首页 > 代码库 > HDU1003 Max Sum
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;
}