# 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);
}
}
```
````
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/lis/300.-longest-increasing-subsequence.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.