【算法思考记录】力扣1423. 可获得的最大点数[Python3, 滑动窗口]
Problem: 1423. 可获得的最大点数
date: “2023-12-03”
问题重述
正难则反，发挥逆向思维，因为最终无法选择的点数是一个连续区间，所以问题可转换成：在一个给定的数组中，我们需要找到移除长度为 n-k 的子数组后，剩余元素的最大总和。这是一个典型的算法问题，其中数据量达到 10^5，要求找到一种高效的解法。
解决思路
初步考虑使用深度优先搜索（DFS）或动态规划，但由于状态定义复杂且效率不高，因此我们转而使用滑动窗口的方法。这种方法不仅简化了问题，还大幅提高了算法的效率。
滑动窗口策略
核心思路是维护一个固定长度为 n-k 的窗口，通过不断移动这个窗口来找出使剩余部分总和最大的子数组。具体步骤如下：
- 计算数组的总和。
- 初始化窗口大小为
n-k。 - 使用两个指针
left和right来标记窗口的左右边界。 - 移动
right指针扩展窗口，直到达到窗口大小。 - 更新最大得分，并逐步移动
left指针来缩小窗口，同时移动right指针继续扫描。 - 在每次移动窗口时，更新并记录最大得分。
窗口大小为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