max Sum(简单动态规划)
max Sum(简单动态规划)
1944864971 发表于2年前
max Sum(简单动态规划)
  • 发表于 2年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

http://acm.hdu.edu.cn/showproblem.php?pid=1003
/
给组测试数据
1
7
2 3 -4 -5 6 7 8
一个关键问题 : 什么时候将开始位置重新赋值
即当连续序列和小于等于零时
/

include

int main()
{
int t;
scanf("%d",&t);
int k=1;
while(t--)
{
int n;
scanf("%d",&n);
int m,max1=-0x3f3f3f3f,start=1,end=1;
int dp=0,temp=1;
for(int i=1; i<=n; i++)
{
scanf("%d",&m);
dp+=m;
if(dp<0)//此时将开始位置重新赋值
{
temp=i+1;//dp是从0开始的 加上一个数仍然小于0 显然这是一个负数 开始位置不能从此开始 至少要从下一个开始
dp=0;//连续序列和又重0开始了
}
if(dp>max1)//比上一个连续序列和大的情况
{
max1=dp;
start=temp;
end=i;
}
}
printf("Case %d:\n%d %d %d\n",k++,max1,start,end);
if(t)printf("\n");//最后一行只有一个换行
}
return 0;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: