最大子序和

輸入一個長度為n的整數(shù)序列，從中找出一段長度不超過m的連續(xù)子序列，使得子序列中所有數(shù)的和最大。

注意： 子序列的長度至少是1。

輸入格式
第一行輸入兩個整數(shù)n,m。
第二行輸入n個數(shù)，代表長度為n的整數(shù)序列。
同一行數(shù)之間用空格隔開。

輸出格式
輸出一個整數(shù)，代表該序列的最大子序和。

數(shù)據(jù)范圍
1≤n,m≤300000
輸入樣例：
6 4
1 -3 5 1 -2 3
輸出樣例：
7

題目不難，我們容易想到暴力枚舉，其時間復雜度是O(n * m)的這顯然是不可取的。
再后我們容易想到用前綴和來枚舉暴力做法。
于是我們有了下面的推斷。將距離小于等于m的一系列前綴和拿出。

我們容易想到，這里面的最大值一定是：最小的減去最大的，當然還要同時滿足最小的在最大的前面。
我們再想一想。這假設上述的條件滿足。
這兩個數(shù)之間有一個數(shù)是有一個數(shù)是大于或者等于這個最大值的，那么這里就矛盾了。最大的差值一定不可能是這兩個，因為前面已經找到更大的數(shù)對了，所以我們可以維護一個區(qū)間隊列，這個區(qū)間隊列是升序的。

#include<iostream> #include<queue> #include<cstdio> using namespace std; typedef long long ll; const int N = 3e5 + 10; ll s[N], n, m; int q[N]; int main() {scanf("%lld %lld", &n, &m);ll temp;s[0] = 0;for(ll i = 1; i <= n; i++) {scanf("%lld", &temp);s[i] = s[i - 1] + temp;}int h = 0, t = 0;ll ans = -0x3f3f3f3f;for(int i = 1; i <= n; i++) {if(i - q[h] > m) h++;ans = max(ans, s[i] - s[q[h]]);while(h <= t && s[q[t]] >= s[i]) t--;//這里保證隊列區(qū)間里的數(shù)是上升的。如果不是上升，從隊尾刪除元素。知道上升為止。q[++t] = i;// printf("%lld\n", ans);}printf("%lld", ans);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的最大子序和：单调队列维护一个上升序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。