题目描述
- 给出一个序列 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章。
-
使用动态规划求解问题，最重要的就是确定动态规划三要素：
- 问题的阶段
- 每个阶段的状态
- 从前一个阶段转化到后一个阶段之间的递推关系。
动态规划算法的一个最经典的问题为<01背包问题>：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。（本题目比01背包问题要简单许多）
如何粗略及初步判断一道题是否为DP？一般说来，只要看题目中选择物体的时候，是可以选取一部分，还是必须整个物体都要选。如果是选取部分，那么就是贪心算法；如果整个物体都要选，那么就是动态规划算法。本题目中序列的某个数，要么不选，要么选，不能选一部分。
- 几个需要注意的地方：
- 如果有多组子序列符合要求，需要输出最前面的那个。
- 注意输出格式，一个字母也不能错。
- 动态规划算法是经典算法，请熟练掌握。
思考题
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;
}
