【算法思考记录】力扣1423. 可获得的最大点数[Java, 滑动窗口]

本文主要是介绍【算法思考记录】力扣1423. 可获得的最大点数[Java, 滑动窗口]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;}
}