【DP复习2】HDU 1003——Max Sum

题目：点击打开链接

这个问题是DP，但是不需要数组就可以做，应用startpos,endpos记录位置。tmp读数，now计算当前记录的和，判当前+读入的数是否小于读入的数，如果越读越小的话，那么就换一个位置，如果增大，说明对MAX是有利的，移动endpos就可以了，最后和maxsum进行比较。

附一组Trick数据：

5 -1 -2 -3 -4 -5答案是 -1 1 1.

#include <iostream>using namespace std;int main(){int testcase;cin>>testcase;for(int i=1;i<=testcase;i++){int n,tmp,tp;int maxnum,startpos,endpos,tstart,now;cin>>n>>tmp;startpos=1;endpos=1;tstart=1;maxnum=tmp;//一定要临时在这里设置一个 now=tmp;for(int j=2;j<=n;j++){cin>>tp;if(now+tp<tp){now=tp;tstart=j;   //临时标记的变量 }else{now+=tp;}if(now>maxnum){maxnum=now;startpos=tstart;endpos=j; }}cout<<"Case "<<i<<":"<<endl;cout<<maxnum<<" "<<startpos<<" "<<endpos<<endl;if(i!=testcase)cout<<endl;}return 0;}