Longest Increasing Subsequence

Posted on by oneOokay

区间型的DP 求max/求solution count

  • 300. Longest Increasing Subsequence
  • 673. Number of Longest Increasing Subsequence

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Dynamic Programming

dp的定义: 接龙型 dp[i] 表示以nums[i]为最后一个数字的LIS的长度

  • 接龙的方法: nums[i]可以接在[0, i-1]中任何一个比nums[i]小的数字之后组成一个LIS
    • 注意这个和Longest Increasing Subarray的区别: 这个是nums[i]只能接在nums[i-1]之后
  • 递推公式:dp[i] = Math.max(dp[x] + 1 ) (当nums[x] < nums[i]时)
  • dp = int[n] 这里n就够了, 因为dp[0]就是nums[0] 值为1
  • 值的初始化: dp[i] = 1 因为在数组不为null和空的情况下，dp[i]最小值为1.
  • res就是dp[i]的max
  • TimeComplexity: O(N2)
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int res = 1;
    for(int i = 1; i < n; i ++) {
        for(int j = 0; j < i; j ++) {
            if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

O(n log n) with Binary Search

用到了Arrays.binarySearch(int[] a, int fromIndex(inclusive), int toIndex(exclusive, int key) 这个method. 每操作一次的时间复杂度是O(logn).需要用n次.

  • 在array的[start, end)中寻找value=key的元素的index:
  • if key exist in the array : returns the index of the key. NOTE:
    • If there are duplicates, there is no guarantee which one will be found.
    • this guarantees that the return value will be >= 0 IF and ONLY IF the key is found.
  • if key does NOT exist in the array: returns (-(insertion point) – 1).
    • insertion point 是指: the index pointer where value would be inserted in to the array.
    • the FIRST element GREATER than the key, OR
    • a.LENGTH if ALL elements in the array are LESS than the specified key.
    • 假设返回x, 那么insertion point = -(x + 1) (NOTE: x < 0)

同样的一个int[] dp, 长度和array一样:不同的是: 这个dp array用来存当前的LIS. 但是并不是一直都是满足条件的LIS的,只有在当前刚刚update的index = i的之前(包括i)的element是满足条件的LIS.(具体看下面) 但是没有关系length这个LIS length一直都是正确的.

e.g.

input: [0, 8, 4, 12, 2]. len 初始化为0 表示dp中LIS length

  1. search(dp, 0, 0, 0) 返回x= -1; 求得insert point i = 0; 把key=0放到dp[0]中. 此时i == len == 0所以len ++. dp: [0]
  2. search(dp, 0, 1, 8): dp中[0, len)的范围(LIS长度范围内)找 8. 返回x=-2, i=1; 把key=8放到dp[1], i==len ==1; len ++ (2) dp: [0, 8]
  3. search(dp, 0, 2, 4): x = -2, i = 1; 把key=4放到dp[1], i != len. len不变. dp: [0, 4]
  4. search(dp, 0, 2, 12): x = -3, i = 2; 把key=12放到dp[2], i == len == 2; len ++ (3). dp: [0, 4, 12]
  5. search(dp, 0, 3, 2): x = -2, i = 1; 把key=2放到dp[1], i != len. len不变. dp: [0 , 2, 12]. 注意这里: 在dp[0 – 1]中才是一个LIS. (此时的插入point为1). (虽然整个dp array是递增的,但是没有按照元素的出现顺序来). 而且可以知道符合条件的LIS其实是在第4步的[0,4,12]. 但是这个没有关系,因为题目要求max length, 3是正确的.
  • 这题要一直在dp的[0, len)的范围内找key
  • 如果key在dp里面, 什么也不用干.
  • 返回len 
public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }        
        int len = nums.length, l = 0;
        int[] dp = new int[len];
        int x = 0, pos = 0;
        for(int i = 0; i < len; i ++){
            x = Arrays.binarySearch(dp, 0, l, nums[i]);//永远传入l
            if (x < 0) {//只关心nums[i] doesn't exist in dp
                pos = - (x + 1);
                dp[pos] = nums[i];
                if(pos == l)
                    l ++;
            }
        }
        return l;
    }

673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

  • 由LIS知: 当nums[i] > nums[x], 把nums[i]加到nums[x]后组成一个更长的LIS时, 我们可以得知
    • 这个以nums[i]为最后一个元素的LIS的length = 以nums[x]为最后一个元素的LIS的length + 1
    • 这个以nums[i]为最后一个元素的LIS的count = 当以nums[x]为最后一个元素的LIS的count
  • 所以用count[i]存count of LIS ends with nums[i] (并且 LIS length = dp[i])
    • 对dp[i]和dp[x] + 1进行判断
      • 当dp[i] == dp[x] + 1 => 说明nums[i]和nums[x]又组成了一个同样长度的LIS => count[i] += count[x]
      • 当dp[i] < dp[x] + 1 => 说明nums[i]和nums[x]组成了一个更长的LIS => count[i] = count[x]
  • 求出max(dp[i])之后, loop through count array: 把dp[i] == max的所有的count[i]相加即为res.

TimeComplexity: O(N2) / Space: O(N)

public int findNumberOfLIS(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n];
    int[] count = new int[n]; 
    int max = 1;
    Arrays.fill(dp, 1);
    Arrays.fill(count, 1);
    for(int i = 1; i < n; i ++) {
        for(int j = 0; j < i; j ++) {
            if (nums[i] > nums[j]) {
                if (dp[i] == dp[j] + 1) {
                    count[i] += count[j];
                } else if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j]; 
                }
            }
        }
        max = Math.max(max, dp[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i ++) {
        if (dp[i] == max)
            res += count[i];
    }
    return res;
}

Leave a comment