当前位置: 代码迷 >> 综合 >> HDU 1003 Max Sum-动态规划
  详细解决方案

HDU 1003 Max Sum-动态规划

热度:54   发布时间:2023-11-06 18:58:32.0

中文题,求最大连续子序列。

思路:

起点从第一个开始累加,如果当前和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;
}