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。