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

Problem: 1423. 可获得的最大点数
date: “2023-12-03”

问题重述

正难则反，发挥逆向思维，因为最终无法选择的点数是一个连续区间，所以问题可转换成：在一个给定的数组中，我们需要找到移除长度为 n-k 的子数组后，剩余元素的最大总和。这是一个典型的算法问题，其中数据量达到 10^5，要求找到一种高效的解法。

解决思路

初步考虑使用深度优先搜索（DFS）或动态规划，但由于状态定义复杂且效率不高，因此我们转而使用滑动窗口的方法。这种方法不仅简化了问题，还大幅提高了算法的效率。

滑动窗口策略

核心思路是维护一个固定长度为 n-k 的窗口，通过不断移动这个窗口来找出使剩余部分总和最大的子数组。具体步骤如下：

1. 计算数组的总和。
2. 初始化窗口大小为 n-k。
3. 使用两个指针 left 和 right 来标记窗口的左右边界。
4. 移动 right 指针扩展窗口，直到达到窗口大小。
5. 更新最大得分，并逐步移动 left 指针来缩小窗口，同时移动 right 指针继续扫描。
6. 在每次移动窗口时，更新并记录最大得分。

窗口大小为0时的特殊情况处理

此时无需维护任何滑动窗口，因为total就是答案本身，直接返回即可。

Python代码实现

class Solution:
    def maxScore(self, cps: List[int], k: int) -> int:
        ans = 0
        total = sum(cps)
        n = len(cps)
        win_size = n - k
        if win_size == 0:
            return total

        left, right = 0, 0
        sub_arr_sum = 0
        while right < n:
            sub_arr_sum += cps[right]  # 加入窗口
            if (right - left + 1) >= win_size:
                ans = max(ans, total - sub_arr_sum)
                sub_arr_sum -= cps[left]
                left += 1
            right += 1
        
        return ans