最长上升子序列(Longest Increasing Subsequence, 简称LIS)是dp中比较经典的一个算法模型, 它有一种朴素的算法O(n^2)和一种优化版的算法O(nlogn)实现, 通过它, 我们可以进一步了解dp的思想。

接下来我们实现O(n^2)的算法LIS_nn()

首先确定状态转移方程 dp[i]代表以第i项为结尾的LIS的长度 

dp[i] = max(dp[i], max(dp[j]) + 1)         if j < i and a[j] < a[i] 

根据上面的状态转移方程可以写出下面的代码

int LIS_nn() {  
    int ans = 0;  
    for (int i = 1; i <= n; ++i) {  
        dp[i] = 1;  
        for (int j = 1; j < i; ++j) {  
            if (a[j] < a[i]) {  //要满足上升的条件
                dp[i] = max(dp[i], dp[j] + 1);  
            }  
        }  
        ans = max(ans, dp[i]);  
    }  
    return ans;  
}  

我们继续思考一下刚才的算法是否还有优化的空间呢？ 

在刚才的内层for我们从前往后找一个最大的LIS值，仔细想一下是否可以发现这个值一定是单调递增的呢? 
由于这个值是单调递增的，所以我们就没必要使用从前往后遍历的方法，可以使用二分查找来优化这个寻找的过程。 

于是可以实现O(nlogn)算法的LIS_nlgn()函数

int LIS_nlgn() {  
    int len = 1;  
    dp[1] = a[1];  
  
    for (int i = 2; i <= n; ++i) {  
        if (a[i] > dp[len]) {  
            dp[++len] = a[i];  
        } else {  
            int pos = lower_bound(dp, dp + len, a[i]) - dp;  
            dp[pos] = a[i];  
        }  
    }  
    return len;  
}  

上面的代码是求最长上升子序列的长度
也可以求最长上升子序列的累加值

最大上升子序列和
题目描述：
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4...

练习题目

DreamJudge 1256 拦截导弹
DreamJudge 1253 合唱队形