题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1087
题目本质上要求我们求给定序列的最长的递增序列，由于刚接触DP，所以一开始还把状态方程写错了，还特地看了运筹学和算法导论的动态规划这一部分。以下是错误的解题历程，读者可以忽略这部分“【 】”。
【（sum[i]保存的是当前求得的最大和, d[i]保存的是第i个数，sum[i] = max{sum[i-1], sum[i-1]+d[i]} 条件是: d[i-1] > d[i]）。接着写成：sum[i] = sum[i-1]+d[i] （d[i-1] < d[i]） (注意：这里的d[i-1]不一定紧挨着d[i]的，它表示的是计算前一个最大和状态sum[i-1]时的最后一个数，即为d[i-1]，那么当前的最大和sum[i]在满足d[i-1] < d[i]这种情况的时候，只能是sum[i-1]+d[i]了
比如说这个序列 ： 1 5 4 98 7 46 3
当i指示的是4这个数时，前一个最大和状态sum[i-1]为 6（1+5的结果，此时d[i-1]为5），但当前的d[i]为4,显然不满足d[i-1] < d[i]，于是i指向下一个位置，即98这个数，满足d[i-1] < d[i]（5 < 98），于是更新新一轮的sum[i]，为104（6+98），i继续向后移动，由于再也找不到比98大的数，所以最终结果是104。如果不满足d[i] > d[i-1]，那么就一直保存前一个状态s[i-1]，直到扫描到序列的最后一个元素。如果这样想，有一种序列是求解不了的，即1 9 4 8 98 110，我写的代码里只能求解1 9 98 110， 不能求解更大的1 4 8 98 110】，无奈之下，看了别人的思路，再加上做01背包（bone collector）的经验，一下子顿悟了。
正确的状态转移方程： sum[i] = max{sum[j]} + d[i] （0 <= j < i && d[j] < d[i]）
要多设一个辅助数组是sum[i]，它的数组下标是和d[i]的数组下标是一致的。保存的是比当前i小的且排在i前面的最大和，例如选定的dp[3] (98)，它可以选的点是下标为 0、 1、 2 的sum值，此时我们是选最大的sum[1](前提是dp[1] < dp[3])，那么加上当前的dp[3]，sum[3] = sum[1] + dp[3]了。这里的阶段实质上是如何得到sum[i]，而它是与当前的dp[i]和sum[j]（j < i）密切相关的。最后再比较sum[i]里的数，最大的那个数即是结果。
假设还是 1 5 4 98 7 46 3 这个序列
数组下标i 0 1 2 3 4 5 6
dp[i] 1 5 4 98 7 46 3
sum[i] 1 6 5 104 13 59 4
1 #include <iostream> 2 using namespace std; 3 4 int main() 5 { 6 int dp[1005], sum[1005], i, j, n, maxsum, msum; 7 while (cin >> n && n) 8 { 9 memset(sum, 0, sizeof(sum)); 10 for (i = 0; i < n; i++) 11 scanf("%d", &dp[i]); 12 sum[0] = dp[0]; 13 for (i = 1; i < n; i++) 14 { 15 msum = 0; 16 for (j = i-1; j >= 0; j--) 17 { 18 if (msum < sum[j] && dp[i] > dp[j]) 19 { 20 msum = sum[j]; 21 } 22 } 23 sum[i] = msum + dp[i]; 24 } 25 maxsum = sum[0]; 26 for (i = 1; i < n; i++) 27 if (maxsum < sum[i]) 28 maxsum = sum[i]; 29 printf("%d\n", maxsum); 30 } 31 return 0; 32 }