题目描述

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。 注意： 子序列的长度至少是1。 输入格式 第一行输入两个整数n,m。 第二行输入n个数，代表长度为n的整数序列。 同一行数之间用空格隔开。 输出格式 输出一个整数，代表该序列的最大子序和。 数据范围 1≤n,m≤300000 输入样例： 6 4 1 -3 5 1 -2 3 输出样例： 7

题解

求某一段序列和，用前缀和来做。维护一段长为m的队列，问题转化为从队列找到最小值。单调队列优化：由题目可知，队列中有些元素永远不会被使用到。比如队列里5， 3 。 3在5的后面，3后面的元素找最小值，由于有3的存在，5不可能是最小值。因此5可以不加入队列里。有这个性质，可以知道队列一定是一个单调队列。 #include <iostream> #include <cstring> #include <algorithm> #include <limits.h> using namespace std; const int N = 300010; int q[N], s[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> s[i]; s[i] += s[i - 1]; } int hh = 0, tt = 0; int res = INT_MIN; for(int i = 1; i <= n; i++) { while(i - q[hh] > m) hh++; //滑动窗口大小大于m，弹出队头元素 while(hh <= tt && s[q[tt]] >= s[i]) tt--; //维护单调队列 res = max(res, s[i] - s[q[hh]]); q[++tt] = i; //满足条件插入到队列中 } cout << res << endl; return 0; }