LongestIncreasingSubSequence

• Medium
• tag: DP, BinarySearch
• similar: LCS

Given [10, 9, 2, 5, 6, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

思路

• 最直接就是brute force, 用O(n^2). 外层循环起点, 内层循环该起点所能达到的LIS.
• DP做法: 和Stanford的一样, 定义P[i]为: 以A[i]结尾并包含A[i]的最长LIS的长度. 那么关系就是: $$P[i] = {max(P[k]+1, P[i])\mid A[k] \le A[i] \land k \in [0,i-1]}$$. 这里P[k]要加上1是因为定义的P[i]为以A[i]结尾并包含A[i]的最长LIS的长度, 所以必须包括A[i], 所以加上1.

O(N^2)的DP

• 虽然是DP, 但是复杂度和brute force一样...
• 我在Lintcode里面也是这么做的, 代码如下

public int lengthOfLISOn2(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] LIS = new int[nums.length];  // the lis end with nums[i]
    int ret = 1;
    for (int i = 0; i < nums.length; ++i) {
      LIS[i] = 1;  // init to be a subsequence with itself
      for (int k = 0; k < i; ++k) {
        if (nums[k] <= nums[i]) {
          LIS[i] = Math.max(LIS[k] + 1, LIS[i]);
        }
      }
      ret = Math.max(ret, LIS[i]);
    }
    return ret;
}

Geek4Geek: O(nlogn)最佳解法

• 原来还有更好的方法. 还是SOF, 以及Geek讲得好.
• 首先观察, 通过几个简单的例子来找到规律.
• 然后定义state为: S[pos]保存: smallest integer that ends an increasing subsequence at pos

• 然后algs就是:

  1. 若A[i]小于S的最小, 则更新最小.
  2. 若A[i]大于S的最大, 则extend.
  3. 否则就找S中的ceil, 即大于A[i]的第一个数的位置, 然后更新.

• 最后S的长度就是LIS的长度. 但是注意: S[]并不一定是LIS解. 只是长度是LIS的长度. 例如: 2,6,3,4,1,2,9,5,8, 最后S = {1,2,4,5,8}

找到LIS

• 现在会了O(nlogn)的解法找length, 但是怎么reconstruct这个LIS呢?
• SOF讲了, 但是还没有实现: TODO