注册网站给谁交钱,怎么做网站的代理商,电脑如何做网站,网站做彩票题干#xff1a;
N个整数组成的循环序列a[1],a[2],a[3],…,a[n]#xff0c;求该序列如a[i]a[i1]…a[j]的连续的子段和的最大值#xff08;循环序列是指n个数围成一个圈#xff0c;因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列#xff09;。当所给的整数均为负数时和为0。…题干
N个整数组成的循环序列a[1],a[2],a[3],…,a[n]求该序列如a[i]a[i1]…a[j]的连续的子段和的最大值循环序列是指n个数围成一个圈因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列。当所给的整数均为负数时和为0。
例如-2,11,-4,13,-5,-2和最大的子段为11,-4,13。和为20。 收起
输入
第1行整数序列的长度N2 N 50000)
第2 - N1行N个整数 (-10^9 S[i] 10^9)
输出
输出循环数组的最大子段和。
输入样例
6
-2
11
-4
13
-5
-2
输出样例
20
解题报告 模板了。
AC代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const LL mod 1e9 7;
const int N 200005;
int a[N];
LL pre[N];
int main() {int n;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);a[n i] a[i];}for (int i 1; i 2 * n; i) {pre[i] pre[i - 1] a[i];}dequeint q;q.push_back(0);LL ans a[1];for (int i 1; i 2 * n; i) {if (!q.empty() q.front() i - n) {q.pop_front();}if(pre[i] - pre[q.front()] ans) {ans pre[i] - pre[q.front()];}else {while (!q.empty() pre[q.back()] pre[i]) {q.pop_back();}}//ans max(ans, pre[i] - pre[q.front()]);q.push_back(i);}printf(%lld\n, ans);return 0;
}
或者
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const LL mod 1e9 7;
const int N 200005;
int a[N];
LL pre[N];
int main() {int n;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);a[n i] a[i];}for (int i 1; i 2 * n; i) {pre[i] pre[i - 1] a[i];}dequeint q;q.push_back(0);LL ans a[1];for (int i 1; i 2 * n; i) {if (!q.empty() q.front() i - n) {q.pop_front();}ans max(ans, pre[i] - pre[q.front()]);while (!q.empty() pre[q.back()] pre[i]) {q.pop_back();}q.push_back(i);}printf(%lld\n, ans);return 0;
}
另一个做法
https://blog.csdn.net/weixin_41544329/article/details/85076111
