中文题,求最大连续子序列。
思路:
起点从第一个开始累加,如果当前和sum小于等于0的话就更改起点,重新累加,最后得到结果。
注意:如果sum等于0的时候没有更改起点的话,虽然算出来最大值不变但是序列比较长。还有要考虑序列全为负数的情况。
#include<iostream>
using namespace std;
int main(){int st,en,k,mx,sum,n,no,ca=0,T;scanf("%d",&T);while(T--){st=en=k=1;sum=0;mx = -1010;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&no);sum+=no;if(sum>mx){mx=sum;st=k;en=i;}if(sum<=0){sum=0;k=i+1;}}printf("Case %d:\n%d %d %d\n",++ca,mx,st,en);if(T) printf("\n");}return 0;
}