1007 Maximum Subsequence Sum (25 分)
最大字段和加记录开始结束位置
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 #include<bits/stdc++.h> 9 using namespace std; 10 int n,a[10005]; 11 int main() 12 { 13 int ans,sum,start,endd,s,e; 14 cin>>n; 15 for(int i=1;i<=n;i++) 16 cin>>a[i]; 17 ans=a[1],sum=a[1]; 18 start=1,s=1; 19 endd=1,e=1; 20 int ss; 21 for(int i=2;i<=n;i++) 22 { 23 ss=sum; 24 sum+=a[i]; 25 if(ss<0)//if(sum<a[i])这么cc写也是对的 26 { 27 start=i; 28 sum=a[i]; 29 } 30 if(sum>ans) 31 { 32 ans=sum; 33 s=start; 34 endd=i; 35 } 36 } 37 if(ans>=0) 38 cout<<ans<<" "<<a[s]<<" "<<a[endd]; 39 else 40 cout<<0<<" "<<a[1]<<" "<<a[n]; 41 return 0; 42 }