首先,如果将题目的“圆环”改成“数组”,相信大家都会做,就是如下
int sum=0,maxn=0;//sum更新最大值
for(int i = 1;i <= n;i++){scanf("%d",&a);if(sum < 0)sum = 0;//当sum小于零时,不如啥都不选sum += a;maxn = max(maxn,sum);
}
printf("%d\n",maxn);
但是此题是一个环。
如果说将数组*2再进行一系列操作,代码更加复杂,但如果将思路转换一下,如果选择一个一定穿过边界($1$或$n$)。如图
如果蓝色部分是最大连续值,那么红色部分一定是最小的连续段!!
所以最后的答案就是max{maxn,cnt-minn}。
Ac Code
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9,mod=INF+7;
int n,cnt,sum,minn=0,a,maxn,sum2;int main()
{scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d",&a);if(sum2 < 0)sum2 = 0;if(sum > 0)sum = 0;sum += a;sum2 += a;cnt += a;minn = min(minn,sum);maxn = max(maxn,sum2);} printf("%d\n",max(cnt-minn,maxn));return 0;
}