本题大意：给定一个长度为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的思路相同，否则你会陷入一个僵局......
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, a[maxn], dp[maxn]; int main () {
while(cin >> n && n) {
memset(dp, , sizeof dp);
for(int i = ; i <= n; i ++)
cin >> a[i];
dp[] = a[];
for(int i = ; i <= n; i ++) {
dp[i] = a[i];
for(int j = ; j < i; j ++)
if(a[i] > a[j])
dp[i] = max(dp[j] + a[i], dp[i]);
}
cout << *max_element(dp, dp + maxn) << endl;
}
return ;
}