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)

Latest

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> dp = new ArrayList<>();
        dp.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < dp.get(0)) {
                dp.set(0, nums[i]);
            } else if (nums[i] > dp.get(dp.size()-1)) {
                dp.add(nums[i]);
            } else {
                int position = binarySerach(dp, nums[i]);
                dp.set(position, nums[i]);
            }
        }
        return dp.size();
    }

    private int binarySerach(List<Integer> dp, int num) {
        int left = 0;
        int right = dp.size() -1;

        while (left <= right) {
            int mid = left + (right - left)/2;
            if (num == dp.get(mid)) {
                return mid;
            } else if (dp.get(mid) < num) { // want right
                if (mid + 1 < dp.size() && dp.get(mid+1) > num) {
                    return mid + 1;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

/***
T: O(nlogn)
dp[i], the the smallest num in  in length (i+1) 

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4

10. (len = 1, the the smallest num in len = 1 is 10)
  
9.  (9 < 10, so replace 10 (replace position depends on!), len = 1, the the smallest num in position 1 is 9)

2.  (2 < 9, so replace 9, len = 1, the the smallest num in position is 2)

2. 5 (5 is bigger than 2 so insert to the end, -> len = 2, the the smallest num in position 2 is 5)

2. 3 (3 < 5, -> len = 2, the the smallest num in len = 2 is 3)

2. 3. 7 (7 is bigger than 3, so insert, -> len = 3, the the smallest num in position 3 is 7)

2. 3  7 101  (101 is bigger than 7, so insert

2. 3. 7. 18 (18 < 101 but > 7, so replace 101) if coming number is 6 -> replace 7(that's why we need bs to find position)


then dp list size is the ans!

so ensure different position's smallest number...
 */

Explaination:

🔍 Goal of Leetcode 300

Given an array nums[], return the length of the longest increasing subsequence (LIS). The brute-force or DP approach is O(n2)O(n^2)O(n2). But this solution runs in O(nlog⁡n)O(n \log n)O(nlogn) using binary search.

---

✅ Core Idea (High-level)

Maintain a list dp, where:

• dp[i] is the smallest possible tail of an increasing subsequence of length i + 1.

---

🧠 Why this works:

Let’s say we build subsequences ending at:

csharpCopyEditLength 1: ends with 2
Length 2: ends with 5
Length 3: ends with 9

This means:

• We have an increasing subsequence of length 3 ending with 9

• If a new number 6 comes in, we could replace 9 with 6 (making it easier to extend future subsequences)

So the idea is: always keep dp as optimized as possible, replacing with smaller values if we can.

---

✨ Breakdown of the code:

🔹 dp.add(nums[0]);

Start with the first number — we’ve found a subsequence of length 1.

🔹 For each nums[i]:

1. If it’s smaller than everything so far:

   javaCopyEditif (nums[i] < dp.get(0))
       dp.set(0, nums[i]);

   → Replace the first element (start new possible LIS).

2. If it's larger than the last element:

   javaCopyEditelse if (nums[i] > dp.get(dp.size()-1))
       dp.add(nums[i]);

   → Extend the LIS.

3. Otherwise:

   javaCopyEditint pos = binarySearch(dp, nums[i]);
   dp.set(pos, nums[i]);

   → Find the first element in dp greater than or equal to nums[i] and replace it to keep the sequence tail as small as possible.

---

🔍 About binarySearch(dp, num)

Your version of binarySerach() is slightly more complicated than necessary. The goal is to find the first element ≥ num.

Here’s a cleaner and more standard version:

javaCopyEditprivate int binarySearch(List<Integer> dp, int num) {
    int left = 0, right = dp.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (dp.get(mid) < num) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

This returns the leftmost index where dp.get(index) >= num, which is what we want to replace.

---

🧪 Example:

nums = [10, 9, 2, 5, 3, 7, 101, 18]

Step-by-step dp:

makefileCopyEditStart: dp = [10]
9 < 10 → dp = [9]
2 < 9 → dp = [2]
5 > 2 → dp = [2, 5]
3 < 5 → dp = [2, 3]
7 > 3 → dp = [2, 3, 7]
101 > 7 → dp = [2, 3, 7, 101]
18 < 101 → dp = [2, 3, 7, 18]

Final dp.size() = 4, so LIS = 4.

---

✅ Final Notes

• dp doesn't store an actual LIS, just helps track the length.

• The trick is: we only replace, never remove — the dp list is always valid.

---

Let me know if you’d like to adapt this code to recover the actual LIS sequence, or if you want a visual animation of how it builds!

4o

You said:

but seems 2, 3, 7, 18 is a LIS?

ChatGPT said:

Yes! You're absolutely right — in the example:

textCopyEditnums = [10, 9, 2, 5, 3, 7, 101, 18]

One possible Longest Increasing Subsequence (LIS) is:

textCopyEdit2 → 3 → 7 → 18

And that's exactly what the algorithm’s dp ends up with at the end:

javaCopyEditdp = [2, 3, 7, 18]

---

🔍 Important clarification:

The dp list does not always represent an actual LIS from the array, but:

It always maintains a list such that:

• Its length equals the length of the LIS,

• And the values are the smallest possible ending values for increasing subsequences of various lengths.

---

🧠 Why this matters:

The real LIS might use different elements from the original array — this greedy + binary search method only gives you the length, not necessarily the actual sequence.

In this case, dp = [2, 3, 7, 18] does happen to be a valid LIS, but:

• That’s a coincidence — it won't always reconstruct the actual sequence.

• It's just a helpful structure to find the length efficiently in O(nlog⁡n)O(n \log n)O(nlogn).

---

🧪 Counter-example:

javaCopyEditnums = [3, 5, 7, 1, 2, 8]

Step-by-step dp:

• 3 → [3]

• 5 → [3, 5]

• 7 → [3, 5, 7]

• 1 → [1, 5, 7] ← replaced 3 with 1

• 2 → [1, 2, 7]

• 8 → [1, 2, 7, 8]

Final dp = [1, 2, 7, 8] LIS length = 4 ✔ But [3, 5, 7, 8] is also a valid LIS — dp doesn't give the original one.

---

✅ Summary

• Yes, in your case dp = [2, 3, 7, 18] is a valid LIS.

• But that’s not guaranteed — dp is a tool to get the LIS length, not necessarily the actual sequence.

Would you like to see how to recover the actual LIS in O(nlog⁡n)O(n \log n)O(nlogn)?

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);
    }
}
```