常州市武进区城乡建设局网站,人力资源管理咨询,安卓apk开发,国外对旅游网站的建设题目描述
输入一个长度为 n#xfffd; 的整数序列#xff0c;从中找出一段不超过 M#xfffd; 的连续子序列#xff0c;使得整个序列的和最大。
例如 1#xff0c;−3,5,1#xff0c;−2,31#xff0c;−3,5,1#xff0c;−2,3#xff1a;
当 m4#x…
题目描述
输入一个长度为 n 的整数序列从中找出一段不超过 M 的连续子序列使得整个序列的和最大。
例如 1−3,5,1−2,31−3,5,1−2,3
当 m44 时S51−23751−237
当 m22 或 m33 时S516516。 输入
第一行两个数 n,m,。
第二行有 n 个数要求在 n 个数找到最大子序和。
输出
一个数数出他们的最大子序和。 样例输入
6 4
1 -3 5 1 -2 3
样例输出
7
#include iostream
#include vector
#include set
#include deque
#include algorithm
using namespace std;
vectorint arr;int main() {int n, k;cin n k;arr.push_back(0);for (int i 1, a; i n; i) {cin a;a a arr[i - 1];arr.push_back(a);}dequeint q;int ans 0;for (int i 0; i n; i) {while (!q.empty() arr[q.back()] arr[i]) q.pop_back();q.push_back(i);if (i - q.front() k) q.pop_front();if (arr[i] - arr[q.front()] ans) ans arr[i] - arr[q.front()];}cout ans;return 0;
}
