Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1230 Accepted Submission(s): 549
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int MAXN=2e6+10; 6 const int INF=1e9+7; 7 int a[MAXN],b[MAXN],c[MAXN]; 8 int min(int a, int b) 9 { 10 return (a>b)?b:a; 11 } 12 int main() 13 { 14 int n; 15 while(~scanf("%d", &n)) 16 { 17 for(int i=0;i<n;i++){ 18 scanf("%d", &a[i]); 19 a[i+n]=a[i]; 20 } 21 for(int i=0;i<n;i++){ 22 scanf("%d", &b[i]); 23 c[i]=a[i]-b[i]; 24 c[i+n]=c[i]; 25 } 26 int p=0,res=-INF; 27 int sum=0,suma=0; 28 int l=0; 29 for(int i=0;i<2*n;i++){ 30 sum+=c[i]; 31 suma+=a[i]; 32 if(suma>res) 33 { 34 res=suma; 35 p=l; 36 } 37 if(sum<0) 38 { 39 sum=0; 40 suma=0; 41 l=i+1; 42 if(l>=n) break; 43 } 44 } 45 printf("%d\n", p); 46 } 47 48 return 0; 49 }
2017ICPC沈阳网络赛 HDU 6025 -- card card card(最大子段和)
原文:http://www.cnblogs.com/MasterSpark/p/7509805.html