Problem
N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。 例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。
Solution
最大字段和最大,或者去掉中间某个最小字段和剩下的最大。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<stdio.h> #include<set> #include<iostream> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int n; ll a[50020]; ll fmn[50020],fmx[50020],mn=0,mx=0,sum; int main() { io_opt; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; fmx[i]=max(a[i],fmx[i-1]+a[i]); mx=max(mx,fmx[i]); fmn[i]=min(a[i],fmn[i-1]+a[i]); mn=min(mn,fmn[i]); } cout<<max(mx,sum-mn); return 0; }
|