AcWing 最大子序和

Description

• 输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。

Input

• 第一行输入两个整数n,m。

  第二行输入n个数，代表长度为n的整数序列。

  同一行数之间用空格隔开。

Output

• 输出一个整数，代表该序列的最大子序和。

Data Size

• 1≤n,m≤300000

Sample Input

6 41 -3 5 1 -2 3

Sample Output

7

题解：

• 单调队列。
• 一般区间和的题都转换成前缀和来做。那么这题的基本元素就确定为前缀和。因为随着下标递增，区间的右边界每次都是固定的，所以只需要左边界最小即可。那么问题就成了“找到一个左端点j，使得sum[j]最小（i - m <= j <= i - 1）”。单调决策自然就出来了。

#include 
    
     #include 
     
      #include 
      
       #define N 300005using namespace std;struct Node {int val, pos;};int n, m, ans = -0x7fffffff;int sum[N];deque
       
         deq;int read(){    int x = 0, f = 1; char c = getchar();    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}    return x *= f;}int main(){    cin >> n >> m;    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + read();    deq.push_back((Node){0, 0});    for(int i = 1; i <= n; i++)    {        while(deq.size() && deq.front().pos <= i - m - 1) deq.pop_front();        while(deq.size() && deq.back().val >= sum[i]) deq.pop_back();        deq.push_back((Node){sum[i], i});        ans = max(ans, sum[i] - sum[deq.front().pos]);    }    cout << ans;    return 0;}