# 300. Longest Increasing Subsequence (LIS)

[https://leetcode.com/problems/longest-increasing-subsequence/](https://leetcode.com/problems/longest-increasing-subsequence/)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhBRZ_H-8BwAiWZFUFS%2F-MhBRrBCJwXa_0TGLVWR%2Fimage.png?alt=media\&token=cd2c67c2-e54b-47d8-8ddd-9f3de4e0d9c7)

## [https://www.youtube.com/watch?v=22s1xxRvy28](https://www.youtube.com/watch?v=22s1xxRvy28)

## 1. DP

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCW-nqij62QSp-OhAvZ%2F-MCW2p1WV3eUbImwx8Rk%2Fimage.png?alt=media\&token=56e2ed04-663b-43c6-9756-6e2aa2560aa0)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCW-nqij62QSp-OhAvZ%2F-MCW2x2jgrE6308aN2Oy%2Fimage.png?alt=media\&token=c031a31d-8bb1-4ef4-93ab-3d835b4603a8)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCW-nqij62QSp-OhAvZ%2F-MCW32lNhKyUCtf_g1Kv%2Fimage.png?alt=media\&token=da55593b-c25c-4709-a41e-19ee7594dabd)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCW-nqij62QSp-OhAvZ%2F-MCW36uscS1Et6hovhUu%2Fimage.png?alt=media\&token=8320a3e8-a630-49a9-87e6-009238647c4d)



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]) {

&#x20;     dp\[i] = Math.max(dp\[i], dp\[j]+1)

}



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

&#x20;所以 j 要在 i 前面, nums\[i] > nums\[j]

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLO1nGMiSk1QWXHrir%2F-MgLTzfLgRkMAQYXbozO%2Fimage.png?alt=media\&token=5fcd811f-3934-46cd-b3a4-3824508ff8bf)

time: O(n^2)

space: O(n)

```java
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

```java
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:**

    ```java
    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:**

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

    → Extend the LIS.
3.  **Otherwise:**

    ```java
    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:

```java
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:

```java
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:

```java
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)?







```java
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

```java
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/](https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgQjlX497KINNN-9tsk%2F-MgQkbAZXcklBSVvbW4Y%2Fimage.png?alt=media\&token=66eaecac-f8e1-470d-b064-2e7f93f1e0b2)

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

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgQjlX497KINNN-9tsk%2F-MgQlFpdFb7xit94yGAN%2Fimage.png?alt=media\&token=7059a492-8277-4745-b07c-0f42cf6f6d90)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgQjlX497KINNN-9tsk%2F-MgQl7W37pJi9-tPRfbK%2Fimage.png?alt=media\&token=41d1079f-3599-4391-8106-03729bb614e3)

## num: 10

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQhj8z1I6JeI0vTzy2%2Fimage.png?alt=media\&token=998edf00-9283-4bb0-bcba-0733ae09f91b)

## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQhowfM9S_XpeZfvdk%2Fimage.png?alt=media\&token=8e4cd027-fd9f-475f-baa8-44f51adf881d)

## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQhtjH2gmY2wbrdM3r%2Fimage.png?alt=media\&token=25bc0c80-ef86-4716-b247-6b8254cdfb31)



## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQhwR_hp2JPkbUy5wj%2Fimage.png?alt=media\&token=44c04738-6cdf-494a-a82e-78e978dc89da)

## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQhzLQIC_y5pEIOO-w%2Fimage.png?alt=media\&token=4a5bb55c-694e-4df3-8a2e-5dedf8518c62)



## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQi10FUM54KV6B6JD6%2Fimage.png?alt=media\&token=39a3af04-e510-4856-9163-dde748843676)



## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQi3izHBaBdRDEM452%2Fimage.png?alt=media\&token=ad4cc062-7ddf-49b4-86d2-4c5dd703dd94)



## 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
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQi6VIG43sDUCmeu9-%2Fimage.png?alt=media\&token=9accd235-c6b9-4c91-b7da-f614e1d94a2b)



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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgLceqixbngmXuPgv2G%2F-MgQi9ApXo_81vPEoRO2%2Fimage.png?alt=media\&token=b706c9a3-6398-46c2-9ada-f91152d6bc0b)



## DFS + memo

O(n^2)

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