> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/lis/300.-longest-increasing-subsequence.md).
# 300. Longest Increasing Subsequence (LIS)
##
## 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)
```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 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 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(nlogn)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 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(nlogn)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(nlogn)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
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
```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);
}
}
```
````