中国空间站模型,项目管理软件有哪些,wordpress批量上传产品,开发公司支付给业主的购房补贴Problem: 1423. 可获得的最大点数 date: “2023-12-03” 问题重述
正难则反#xff0c;发挥逆向思维#xff0c;因为最终无法选择的点数是一个连续区间#xff0c;所以问题可转换成#xff1a;在一个给定的数组中#xff0c;我们需要找到移除长度为 n-k 的子数组后#… Problem: 1423. 可获得的最大点数 date: “2023-12-03” 问题重述
正难则反发挥逆向思维因为最终无法选择的点数是一个连续区间所以问题可转换成在一个给定的数组中我们需要找到移除长度为 n-k 的子数组后剩余元素的最大总和。这是一个典型的算法问题其中数据量达到 10^5要求找到一种高效的解法。
解决思路
初步考虑使用深度优先搜索DFS或动态规划但由于状态定义复杂且效率不高因此我们转而使用滑动窗口的方法。这种方法不仅简化了问题还大幅提高了算法的效率。
滑动窗口策略
核心思路是维护一个固定长度为 n-k 的窗口通过不断移动这个窗口来找出使剩余部分总和最大的子数组。具体步骤如下
计算数组的总和。初始化窗口大小为 n-k。使用两个指针 left 和 right 来标记窗口的左右边界。移动 right 指针扩展窗口直到达到窗口大小。更新最大得分并逐步移动 left 指针来缩小窗口同时移动 right 指针继续扫描。在每次移动窗口时更新并记录最大得分。
窗口大小为0时的特殊情况处理
此时无需维护任何滑动窗口因为total就是答案本身直接返回即可。
Java代码实现
class Solution {public int maxScore(int[] cardPoints, int k) {int n cardPoints.length;int winSize n - k;int total 0;for (int cardPoint : cardPoints) {total cardPoint;}if (winSize 0) {return total;}int winSum 0, ans 0, left 0, right 0;while (right n) {winSum cardPoints[right];if (right - left 1 winSize) {ans Math.max(ans, total - winSum);winSum - cardPoints[left];left;}right;}return ans;}
}
