Description

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

第一行两个数n,m（n,m<=300000） 第二行有n个数，要求在m个数内找到最大子序和

Output Format

一个数，数出他们的最大子序和

6 4
1 -3 5 1 -2 3​

7​

Hint

前缀和最大的优点就是求连续区间的值： a[10]={0,1,2,3,4,5,6,7,8,9};

b[10]={0,1,3,6,10,15,21,28,36,45}; 我们可以发现b[5]-b[2]=15-3=12=a[3]+a[4]+a[5] 这样我们就可以利用前缀和来解决这个问题

#include <iostream>
using namespace std;
#define ll long long
const int maxn = 300050;
int n, m;
int a[maxn], b[maxn];
ll sum = -0x3f3f3f;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = a[i - 1] + a[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= i + m; j++)
            if (a[j] - a[i] > sum)
                sum = a[j] - a[i];
    }
    cout << sum;
    return 0;
}

Source

单调队列 前缀和