[Acwing] 最大子序和 单调队列优化

前言

本题链接 : 滑动窗口 : 维护一个大小为 k k k 的 区间的 最大值和 最小值

思路

取 f [ i ] f[i] f[i]表示 以 a [ i ] a[i] a[i]结尾,长度不超过 m m m最大值

对于区间和 : 我们可以用前缀和维护 s u m [ r ] − s u m [ l ] sum[r] - sum[l] sum[r]−sum[l]

因此暴力做法 可以对于每一个 i i i我们都枚举左端点 :

f [ i ] = m a x ( S [ i ] − S [ j ] ) ( 1 < = i − j < = m ) f[i] = max(S[i] - S[j]) (1