看了一些别人的题解,说实话,我现在还不会证明这个,我不知道为什么这样是最大值
//hdu1003最大连续子序列和 // sum[i] = sum[i-1]>0 ? sum[i-1]+a[i]:a[i]; //只有当sum处于增长状态时才会得到最大子序列 //当sum处于减小状态时,应当更新起点 #include <iostream> using namespace std; #define MAX 100003 #define INF 0x7fffffff; int T; long N; int input,beg,end,sum,max_sum,pos; //定义输入值,最长序列启始和终至位置 ,序列当前和,序列最大和 int main() { cin>>T; for(int i = 1; i <= T; i++) { sum = 0; max_sum = -INF; beg = end = pos = 1; cin>>N; for(int j = 1; j <= N; j++) { cin>>input; if(sum < 0) { sum = input; pos = j; } else { sum += input; } if(sum > max_sum) //更新序列信息 { max_sum = sum; beg = pos; end = j; } } cout<<"Case "<<i<<":"<<endl; cout<<max_sum<<" "<<beg<<" "<<end<<endl; if(i != T) //PE若干次,千万要注意 cout<<endl; } return 0; }