HDU1003 Max Sum

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题意：给你一组数字，求出最大的字段和。

思路：这是一个经典的dp题目，定义数组a储存一组数字，a[j]为ji个数，dp[j]表示已j结尾的最大字段和，那么dp[j]=max(dp[j-1]+a[j],dp[j]).

例如：

a[] 6 -1 5 4 -7

dp[] 6 5 10 14 7

代码如下:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=100005;
int a[N];
int dp[N];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    int n,t,maxbegin,maxend,MAX,MAXbegin,MAXend;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>n;
        for(int j=1;j<=n;j++)
                cin>>a[j];
        MAX=dp[1]=a[1];
        maxbegin=maxend=1;           //标记dp[j]为最大值时的起始位置和末尾位置
        MAXbegin=MAXend=1;          //标记所有dp[j]中为最大时的起始位置和末尾位置
        for(int j=2;j<=n;j++)
            {
               if(dp[j-1]+a[j]>=a[j])
                  maxend=j;
               else maxend=maxbegin=j;
               dp[j]=max(a[j],dp[j-1]+a[j]);
               if(dp[j]>=MAX)
               {
                   MAXbegin=maxbegin;
                   MAXend=maxend;
                   MAX=dp[j];
               }
            }
        cout<<"Case "<<i<<':'<<endl;
        cout<<MAX<<' '<<MAXbegin<<' '<<MAXend<<endl;
        if(i!=t)
            cout<<endl;
    }
    return 0;
}

相关推荐