0X00 算法總結(jié)
最大子序和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 0: return 0
m = len(nums)
# dp 問(wèn)題以結(jié)尾分集合
# dp[i] 表示以 i 結(jié)尾的最大連續(xù)子序和
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
這是一道非常經(jīng)典的 dp 問(wèn)題, 以最大子序和的最后一個(gè)數(shù)字來(lái)劃分集合
- dp[i] 表示以 i 結(jié)尾的最大連續(xù)子序和
轉(zhuǎn)移方程:
- dp[i] = max(dp[i-1] + nums[i], nums[i])
窗口大小限制的最大子序和
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)
用「單調(diào)隊(duì)列」來(lái)解決這一方面的問(wèn)題
使用「前綴合」以后發(fā)現(xiàn)固定最后一位, 減去前面前不超過(guò)窗口大小的最小的一位, 就是以 i 結(jié)尾的最大子序列和
