【每周一题】2017.3.13 HDU1003 解题报告

题目描述

• 给出一个序列 a[1]，a[2]，a[3]......a[n]， 请计算出它的子序列的最大值。 子序列就是该序列的任意一个子串。例如，序列 (6,-1,5,4,-7)，子序列的最大值为 6 + (-1) + 5 + 4 = 14。【提示：请参考经典算法中的<01背包问题>】
• 可以把代码提交至这里：http://acm.hdu.edu.cn/showproblem.php?pid=1003

解题分析

• 看完题目后的五秒钟，你马上冷静地意识到，这道题是有顺序性的。从第一个数开始，如果是正数就一直累加，遇到负数怎么办？重新开始累加？把之前最大的累加和记下来？好像有点懵…………你的思路是对的！但还需要一点深入思考。

• 假设我们有一个函数F(x)。它表示序列中以第x个数为结尾的子序列的最大和，比如序列(1，-2，3)，那么F(1)=1，F(2)=-1，F(3)=3。这个函数非常神奇，因为它是一个递推函数——想求F(x+1)怎么办？简单啊！F(x+1)表示序列中以第x+1个数为结尾的子序列的最大和，我们已经有F(x)了，那么有：

F(x+1)=F(x)+a[x+1]

• 其中a[x+1]表示序列中的第x+1个数。

• 等等，好像有点问题。如果F(x)是个负数，它岂不是把F(x+1)变得更小了？那么它就失去了最大和的意义。这种情况下，F(x+1)直接等于a[x+1]更合适，也就是说，序列中以第x+1个数为结尾的子序列的最大和，要么等于以x结尾的最大和加上第x+1个数，要么就直接等于第x+1个数，没有其他的可能性。 即：

F(x+1)=Max(F(x)+a[x+1],a[x+1])

• 好了，那么我们只需要从序列的第一个数开始推起，一直推到F(n)，然后找出F(1)...F(n)中的最大值，就是我们想要的结果。题目还需要输出子序列的起始位置，只需要在每次决策时，记录下开始位置即可。

• 如果你还是很懵，给你五分钟消化一下。

算法分析

• 这道题是一个非常典型的动态规划题。还记得上次的贪心算法吗？与贪心算法不同的是，动态规划算法在每次决策时，不能选择局部最优解，而是采用递推的方法，逐步地从子问题推出全局最优解。动态规划的详细讲解此处不再赘述，请自行学习《算法导论》中的第15章。

• 使用动态规划求解问题，最重要的就是确定动态规划三要素：

  1. 问题的阶段
  2. 每个阶段的状态
  3. 从前一个阶段转化到后一个阶段之间的递推关系。

• 动态规划算法的一个最经典的问题为<01背包问题>：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。（本题目比01背包问题要简单许多）

• 如何粗略及初步判断一道题是否为DP？一般说来，只要看题目中选择物体的时候，是可以选取一部分，还是必须整个物体都要选。如果是选取部分，那么就是贪心算法；如果整个物体都要选，那么就是动态规划算法。本题目中序列的某个数，要么不选，要么选，不能选一部分。

• 几个需要注意的地方：
  1. 如果有多组子序列符合要求，需要输出最前面的那个。
  2. 注意输出格式，一个字母也不能错。

• 动态规划算法是经典算法，请熟练掌握。

思考题

1. 这道题的时间复杂度和空间复杂度是多少？
2. 请写出这道题的动态规划三要素。

例程（C++）

（注：例程只是给出一种解题方法，不是标准程序，也不一定是最完美的解法）

//HDU 1003 by Xinjie Wang

#include <iostream>
using namespace std;

const int MAXLENGTH = 100001;
int numArr[MAXLENGTH], dp[MAXLENGTH], startPos[MAXLENGTH];

int main()
{
    int totalCase = 0;
    cin >> totalCase;
    for (int caseIter = 1; caseIter <= totalCase; caseIter ++)
    {
        if (caseIter > 1) cout << endl;
        cout << "Case " << caseIter << ":" << endl;
        
        int num = 0;
        cin >> num;
        //read inputnumbers - O(N)
        for (int i = 0; i < num; ++i)
        {
            cin >> numArr[i];
            dp[i] = 0;
            startPos[i] = 0;
        }

        //start dp function : dp[i] = MAX(dp[i - 1] + numArr[i], numArr[i])
        dp[0] = numArr[0];
        startPos[0] = 0;
        int maxNum = dp[0], retStart = 0, retEnd = 0;
        for (int i  = 1; i < num; ++i)
        {
            if (dp[i - 1] + numArr[i] >= numArr[i])
            {
                dp[i] = dp[i - 1] + numArr[i];
                startPos[i] = startPos[i - 1];
            }
            else
            {
                dp[i] = numArr[i];
                startPos[i] = i;
            }

            if (dp[i] > maxNum)
            {
                maxNum = dp[i];
                retStart = startPos[i];
                retEnd = i;
            }
        }
        cout << maxNum << " " << retStart + 1 << " " << retEnd + 1 << endl;
    }
    return 0;
}