本文主要是介绍HDU1003 Max Sum【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1003
题目大意：
求使连续子序列的和最大的第一元素，最后一个元素位置，和子序列的和
思路：
动态规划的方法，主要是找到状态转移方程。将之前累加和加上当前值与当前值做比较，
如果将之前累加和加上当前值>当前值，那么加上当前值，最后一个元素位置变为i，如果
将之前累加和加上当前值<当前值，那么sum[i] = a[i],并且改变第一元素位置为i，最后元
素位置为i。具体看代码。状态转移方程：sum[i]=max(sum[i-1]+a[i],a[i]);
AC代码：
<span style="font-family:Microsoft YaHei;font-size:18px;"># include<stdio.h>
# include<string.h>
int num[100010];int main()
{int i,T,N,sum,max,t,a,b,a1,b1;scanf("%d",&T);t = 1;while(T--){ scanf("%d",&N);memset(num,0,sizeof(num));for(i=0;i<N;i++)scanf("%d",&num[i]);max = sum = num[0];a1 = b1 = a = b = 1;for(i=1;i<N;i++){if(num[i]>sum+num[i]){sum = num[i];a = i+1;b = i+1;}else{sum += num[i];b = i+1;}if(max<sum){max = sum;a1 = a;b1 = b;} }printf("Case %d:\n%d %d %d\n",t++,max,a1,b1);if(T)printf("\n");}return 0;
}</span>这篇关于HDU1003 Max Sum【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
