本题大意：给定一个长度为n的序列a，让你输出这个序列子序列中元素和最大的最大上升子序列。
本题思路：一开始肯定可以想到用LIS实现，我们用LIS实现的时候可以发现这个问题并不满足LIS问题的最优子结构，即两者的子问题肯定是不相同的...比如5 2 2 2 1 2 3，在这五个数中，如果按照LIS你会发现dp[3] = 2 ，dp[ 4] = 2，那么dp[5]呢，dp[5] = 3，刚好是不满足LIS求解的性质的，也就是违反了LIS的最优子结构性质，那么我们要如何才能得到另一份最优子结构呢，我看可以看到dp[4] = dp[3] + a[4] ，那么也就是如果我们assume dp[ i ] instead of 以i结尾的最大上升子序列，那么就可以得到一个状态转移方程dp[ i ] = max(dp[ j ] + a[ i ], dp[ i ])(j < i)，接下来看代码......
千万不要认为局部LIS和整体LIS的思路相同，否则你会陷入一个僵局......
参考代码：
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 1000 + 5; 7 int n, a[maxn], dp[maxn]; 8 9 int main () { 10 while(cin >> n && n) { 11 memset(dp, 0, sizeof dp); 12 for(int i = 1; i <= n; i ++) 13 cin >> a[i]; 14 dp[1] = a[1]; 15 for(int i = 2; i <= n; i ++) { 16 dp[i] = a[i]; 17 for(int j = 1; j < i; j ++) 18 if(a[i] > a[j]) 19 dp[i] = max(dp[j] + a[i], dp[i]); 20 } 21 cout << *max_element(dp, dp + maxn) << endl; 22 } 23 return 0; 24 }
HDU-1087.SuperJUmpingJUmpingJumping.(DP and LISPP)
原文：https://www.cnblogs.com/bianjunting/p/10623808.html
