`
lovnet
  • 浏览: 6671866 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HDU 1003 Max Sum(最大连续子序列和)

 
阅读更多

题目链接:Click here~~

题意:

RT。

解题思路:

比较简单的dp,很容易推出状态转移方程:sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大连续和.)

然后用一个值记录更新sum[i]的最大值即可。

即对于a[i]这个数字,我们考虑是否将它选入之前连续的序列。

如果选,状态变为sum[i-1]+a[i] ;如果不选,则从此开始一个新的序列,故和为a[i]。

理解方程后,代码很好写了。

#include <stdio.h>
int main()
{
    int z,n,max,sum;
    int a,b,A,B,t;
    scanf("%d",&z);
    for(int k=1;k<=z;k++)
    {
        scanf("%d",&n);
        sum = max = -1001;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            if(sum+t < t)
                sum = t , a = b = i;      //a、b记录当前连续子序列的起始、结束位置
            else
                sum += t , ++b;
            if(max < sum)
                max = sum , A = a , B = b;
        }
        printf("Case %d:\n%d %d %d\n",k,max,A,B);
        if(k-z) puts("");
    }
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics