最长连续子序和问题

0X00 算法总结

最大子序和

53. 最大子序和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0

        m = len(nums)

        # dp 问题以结尾分集合
        # dp[i] 表示以 i 结尾的最大连续子序和
        dp = [0] * 2
        dp[0] = nums[0]
        ans = dp[0]
        for i in range(1, m):
            n = nums[i]
            dp[i & 1] = max(dp[(i-1) & 1]+n, n)
            ans = max(ans, dp[i & 1])
        
        return ans

这是一道非常经典的 dp 问题, 以最大子序和的最后一个数字来划分集合

• dp[i] 表示以 i 结尾的最大连续子序和

转移方程:

• dp[i] = max(dp[i-1] + nums[i], nums[i])

窗口大小限制的最大子序和

135. 最大子序和

n, m = map(int, input().split())
nums = list(map(int, input().split()))

sums = [0] * (n+1)

for i in range(1, n+1):
    sums[i] = sums[i-1] + nums[i-1]

from collections import deque

# print(sums)

deq = deque([0])

res = sums[1]
for i in range(1, n+1):
    if i - m > deq[0]: deq.popleft()
    res = max(res, sums[i] - sums[deq[0]])
    while len(deq) > 0 and sums[i] <= sums[deq[-1]]:
        deq.pop()
    deq.append(i)
print(res)

用「单调队列」来解决这一方面的问题

使用「前缀合」以后发现固定最后一位, 减去前面前不超过窗口大小的最小的一位, 就是以 i 结尾的最大子序列和