300. Longest Increasing Subsequence (LIS)

https://leetcode.com/problems/longest-increasing-subsequence/

https://www.youtube.com/watch?v=22s1xxRvy28

1. DP

O(n^2)

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], 
therefore the length is 4. 

從原題可以看出來, 要找到最長遞增子序列

一定會基於前面的狀態

if (nums[i] > nums[j]) {

dp[i] = Math.max(dp[i], dp[j]+1)

}

• 初始狀態：

  • dp[i] 所有元素置 1，含義是每個元素都至少可以單獨成為子序列，此時長度都為 1。

所以 j 要在 i 前面, nums[i] > nums[j]

time: O(n^2)

space: O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null && nums.length == 0) return 0;
        
        int dp[] = new int[nums.length];
        Arrays.fill(dp, 1);
        
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    // 代表 i 比前面的 j 大時, dp[j]+1
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
/*
 因為是 subseq, 所以不會有什麼 -1 的狀態, i 要跟前面所有狀態都比過（j),
 然後最長的結果可能在某些 dp 裡, 所以要在所有結果中找 max => res = Math.max(res, dp[i]);
*/

greedy + binary search

time: O(nlogn)

space: O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length]; //
        int res = 0;
        for(int num : nums) {
            int i = binarySearch(tails, res, num); // find which index can be smaller (長度為 i 的 subsequence 的最小尾巴值
            tails[i] = num; // update smaller num in tails index i
            if(res == i) res++; // if find i == res, means in the last, so it can be longer subsequence

        }
        return res;
    }
    private int binarySearch(int tails[], int res, int num) {
        int left = 0;
        int right = res;
        while (left < right) {
            int mid = left + (right - left)/2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

readable version

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 0;
        int tails[] = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            
            if (len == 0 || num > tails[len - 1]) {
                tails[len++] = num;
            } else {
                int position = findPositionToReplace(tails, len, num);
                tails[position] = num;
            }
        }
        return len;
    }
    private int findPositionToReplace(int tails[], int res, int num) {
        int left = 0;
        int right = res;
        while (left < right) {
            int mid = left + (right - left)/2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

idea : Patience Sort

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

dp[0] means length 1's 結尾最小的 LIS

dp[1] means length 2 結尾最小的 LIS

num: 10

num:10
tails[0]:10
res == j? => j:0, res:0
==============res++=1

num: 9

num:9
cal m i:0, j:1
m:0
else tails[m] >= num, j = m
after i:0, j:0
tails[0]:9
res == j? => j:0, res:1
==============res++=1

num: 2

num:2
cal m i:0, j:1
m:0
else tails[m] >= num, j = m
after i:0, j:0
tails[0]:2
res == j? => j:0, res:1
==============res++=1

num: 5

num:5
cal m i:0, j:1
m:0
tails[m] < num, i = m + 1
after i:1, j:1
tails[1]:5
res == j? => j:1, res:1
==============res++=2

num: 3

num:3
cal m i:0, j:2
m:1
else tails[m] >= num, j = m
after i:0, j:1
cal m i:0, j:1
m:0
tails[m] < num, i = m + 1
after i:1, j:1
tails[1]:3
res == j? => j:1, res:2
==============res++=2

num: 7

num:7
cal m i:0, j:2
m:1
tails[m] < num, i = m + 1
after i:2, j:2
tails[2]:7
res == j? => j:2, res:2
==============res++=3

num: 21

num:21
cal m i:0, j:3
m:1
tails[m] < num, i = m + 1
after i:2, j:3
cal m i:2, j:3
m:2
tails[m] < num, i = m + 1
after i:3, j:3
tails[3]:21
res == j? => j:3, res:3
==============res++=4

num: 18

num:18
cal m i:0, j:4
m:2
tails[m] < num, i = m + 1
after i:3, j:4
cal m i:3, j:4
m:3
else tails[m] >= num, j = m
after i:3, j:3
tails[3]:18
res == j? => j:3, res:4
==============res++=4

tails:[2, 3, 7, 18, 0, 0, 0, 0]

DFS + memo

O(n^2)

```java
class Solution {
    public int lengthOfLIS(int[] nums) {
        Integer[][] memo = new Integer[nums.length][nums.length];
        return dfs(nums, -1, 0, memo);
    }
    private int dfs(int[] nums, int prev, int cur, Integer[][] memo) {
        if (cur == nums.length) {
            return 0;
        }
        if (prev != -1 && memo[prev][cur] != null) {
            return memo[prev][cur];
        }
        int increasing = 0;
        if (prev == -1 || nums[cur] > nums[prev]) {
            increasing = 1 + dfs(nums, cur, cur+1, memo);
        }
        int notIncreasing = dfs(nums, prev, cur+1, memo);
        if (prev != -1) {
            memo[prev][cur] = Math.max(increasing, notIncreasing);
        }
        return Math.max(increasing, notIncreasing);
    }
}
```