AcWing 135 最大子序和(前缀和,单调队列)

题目链接

解题思路

??枚举右端点,利用前缀和计算\(max(pre[r] - min(pre[l])), l \epsilon [r-m,r-1]\)。所以关键就是如何在范围内找到\(min(pre[l])\),对于范围内的前缀和来说,如果靠右的前缀和比靠左的小,那就肯定用不到他,而如果比靠左的大,如果左边的超出了范围,那么它就可能是一个新的最小值,所以队列里的数就有单调性,可以用单调队列来优化。

代码

const int maxn = 3e5+10;
int n, m;
ll pre[maxn];
deque<int> dq;
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1; i<=n; ++i) {
        scanf("%lld",&pre[i]);
        pre[i] += pre[i-1];
    }
    ll ans = pre[1];
    for (int i = 2; i<=n; ++i) {
        if (!dq.empty() && dq.front()<i-m) dq.pop_front();
        while (!dq.empty() && pre[dq.back()] >= pre[i-1]) dq.pop_back();
        dq.push_back(i-1);
        ans = max(ans, pre[i]-pre[dq.front()]);
    }
    printf("%lld\n",ans);
    return 0;
}

AcWing 135 最大子序和(前缀和,单调队列)

上一篇:搭建高可用mongodb集群(四)—— 分片


下一篇:(日常记录 高德api)+第二周工作总结【总结+看一下】】