HDOJ(HDU).1003 Max Sum (DP)

HDOJ(HDU).1003 Max Sum (DP)

点我挑战题目

算法学习—–动态规划初探

题意分析

给出一段数字序列,求出最大连续子段和。典型的动态规划问题。

用数组a表示存储的数字序列,sum表示当前子段和,maxsum表示最大子段和。不妨设想:当sum为负数的时候:

1.当下一个数字a[i]为正数的时候,sum+a[i] < a[i],不如将sum归零重新计算

2.当下一个数字为负数的时候,sum+a[i]< 0 ,若再下一个数字还为负数,依旧可以得出和小于零……直到遇到一个正数,此时回到1的情况,不如将sum归零计算。

综上所述,当sum为负数的时候,归零

那么再看sum为正数的时候:

1.当下一个数字a[i]为正数的时候,当然选择加上a[i],并且可以更新maxsunm;

2.当下一个数字a[i]为负数的时候,由于不知道后面数字的情况,无法做出决策。

综上所述,当sum>maxsum的时候,要更新maxsum,并且一直累加a[i]

题目还要求输出这个子段的start位置和end位置。可以用x,y分别表示当前最优(大)的子段的开始和结束位置,然后再用sta和ed变量表示当前子段的开始和结束位置。结合上面的叙述:

1.当sum>maxsum的时候,即需要更新的时候,就要更新x和y的位置;

2.当sum< 0的时候,即需要使sum归零计算的时候,就需要把sta的位置置为i+1(指向下一个位置的数字);

以上分析过程就是DP的过程,不难设计出程序。

代码总览

/*
Title:HDOJ.1003
Author:pengwill
Date:2017-2-15
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define nmax 100005
using namespace std;
int a[nmax];
int main()
{
int t;
scanf("%d",&t);
for(int i = 1; i<= t; ++i){
if(i!=1) printf("\n");
printf("Case %d:\n",i);
int n,maxsum = 0,sum = 0,x =1, y=1,sta = 1, ed = 1;
scanf("%d",&n);
for(int i = 1;i <=n; ++i) scanf("%d",&a[i]);
maxsum = -1001;//2.将maxsum初始为-1001
sum = 0;
for(int i =1; i<=n; ++i){
sum+=a[i];ed = i;
if(sum>maxsum){//1.注意此处2个if的位置不能颠倒
maxsum = sum;
x = sta; y = i;
}
if(sum <0){
sta = i+1;
sum = 0;
}
}
printf("%d %d %d\n",maxsum,x,y);
}
return 0;
}

结合代码中的注释:

1.2个if不能颠倒:代码中第二if是指,若sum< 0则舍弃重新计算。但是我们考虑全为负数的情况,如:5 -1 -2 -3 -4 -5 -5,明显这组数据的maxsum应该是-1,若将第二个if放到前面,则无法更新maxsum。

2.将maxsum置为-1001也是考虑数据全为负数的情况,因为题目中还说到数字最小是-1000。

上一篇:(转载)JavaWeb学习总结(五十)——文件上传和下载


下一篇:Java并发学习之二——获取和设置线程信息