- Sample Input 6 -2 11 -4 13 -5 -2 Sample Output
- 20
首先是最基本的, 不是循环的求法:
- #include<stdio.h>
- #include<string.h>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- long long a[50010],b,sum;
- int main()
- {
- int n;
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- cin>>a[i];
- for(int j=0;j<n;j++){
- if(b>0){
- b=b+a[j];
- }
- else{
- b=a[j];
- }
- if(b>sum)
- sum=b;
- }
- cout<<sum<<endl;
- return 0;
- }
这个题分为两种情况: 1: 取中间段 2: 取尾到头的循环段
对于第一种情况, 只需要用上面代码模板即可. 对于第二种情况, 取到循环段, 说明中间某一段没有要, 这一段一定是小于 0 的, 而且其绝对值最大. 所以把数组取反, 求出最大区段和, 用总和减去它再和第一种情况相比较, 取最大就好了.
- #include<stdio.h>
- #include<string.h>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5+10;
- ll a[maxn];
- int main()
- {
- int n;
- cin>>n;
- ll all=0;
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- all+=a[i];
- }
- ll sum=0;ll b=0;
- for(int i=0;i<n;i++) //4 1 2 -1 3
- {
- if(b>0)
- b+=a[i];
- else
- b=a[i];
- if(b>sum)
- sum=b;
- }
- ll sum2=0,b2=0;
- for(int i=0;i<n;i++)
- {
- a[i]=-a[i];
- if(b2>0)
- b2+=a[i];
- else
- b2=a[i];
- if(b2>sum2)
- sum2=b2;
- }
- cout<<max(sum,all+sum2)<<endl;
- }
来源: http://www.bubuko.com/infodetail-3416875.html