# 刷題筆記 - LeetCode 300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence
## Thoughts
給一個整數的 array `nums`，回傳最長的嚴格遞增子序列
subsequence != subarray
也就是說，有的數字是可以跳過的，只要最後回來的會是符合順序的序列
Example 1:
>Input: nums = [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.
Example 2:
>Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
>Input: nums = [7,7,7,7,7,7,7]
Output: 1
以例子 1 來看：` [10,9,2,5,3,7,101,18]`
2 開頭，5 可以跳過，所以最長的子序列長度會是 4 - `[2,3,7,101]` or `[2,3,7,18]`
## Solution 1 - DP
### Logic
反過來思考
>如果以 `dp[i]` 為結尾的嚴格遞增子序列長度會是多少？
假設一個 DP array
```
dp = [1] * len(nums)
```
初始值為 1，因為最短的子序列長度會是 1 (自己)
\
如果要檢查 **自己** 為結尾的子序列長度為何
那就是把自己的位置當作終點，從頭開始檢視（第二層迴圈: `0 ~ i`）
第二層迴圈的 index 假設用 `j`，第一層 index 假設用 `i`
如果 `nums[j] < nums[i]` => **表示 `nums[i]` 可以接在 `nums[j]` 後面遞增**
而 `dp[j]` 代表的是**以位置 `j` 的元素作為結尾的子序列長度**
若可以再增加一個 `nums[i]`
那就表示**以位置 `i` 的元素作為結尾的子序列長度，`dp[i]` = `dp[j] + 1`** => 即**之前的子序列長度加上我所在的這個元素(長度 1)**
邏輯可以寫成
```
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
```
因為第二層迴圈會去檢查 `i` 之前的所有位置，也就是會有多個 `j`
我們要選擇最長的那個子序列
### Code
```python!=
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(0, i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
因 `dp[i]` 代表的是以該位置為結尾的子序列最大的長度，所以答案就是`max(dp)`
### Time & Space complexity
- Time: O(n^2)
- Space: O(n)
## Solution 2 - Binary Search
### Logic
如果照順序遍歷 `nums`，實際上做的事就是確認誰是最小的數字，加到某個 sub array 中，接下來看下一個數字是不是比之前的數字大，如果比之前的數字還小，就找位置替換掉它，比之前的數字大，就可以塞進 sub array
e.g.
```
nums = [10, 9, 2, 5, 3, 7, 101, 18]
```
維護一個 array `sub`
```
[10] → 加入 10
[9] → 9 替換 10（因為 9 比 10 小）
[2] → 2 替換 9
[2, 5] → 5 > 2 → 塞進 sub
[2, 3] → 3 替換 5
[2, 3, 7] → 7 > 3 → 塞進 sub
[2, 3, 7, 101] → 101 > 7 → 塞進 sub
[2, 3, 7, 18] → 18 替換 101
```
整個過程其實是維持 `sub` 的遞增性，去找可以插入 `nums[i]` 的地方
遍歷完整個 `nums`，`sub` 的長度就會是最長的嚴格遞增子序列
\
所以重點在，遍歷 `nums` 時，我要怎麼找到正確的位置來替換原本 `sub` 中的元素，然後在什麼條件下，我可以將 `nums[i]` 塞進 `sub` 中？
\
這邊就要利用 Binary Search，找出目標 array 中，可以塞進 target number 的位置，也就是要找到第一個 array[x] >= target number
這邊放上 Python 的套件 `bisect.bisect_left` 的用法
```
bisect.bisect_left(arr, target)
```
> 在排序好的 `arr` 中，回傳第一個 `>= target` 的位置
e.g.
```python!
import bisect
arr = [2, 3, 5, 7]
print(bisect.bisect_left(arr, 4)) # 回傳 2 → arr[2] = 5, 為第一個 >= 4 的位置
print(bisect.bisect_left(arr, 5)) # 回傳 2 → arr[2] = 5, 為第一個 >= 5 的位置
print(bisect.bisect_left(arr, 8)) # 回傳 4 → 沒有任何元素 >= 8，回傳 len(arr) 也就是插入的位置為最後
```
因此過程就是
1. 遍歷整個 `nums`，利用二分搜尋法去找 `sub` 中，可以插入目前數字的位置
2. 若使用 `bisect_left` 回傳的值是 `len(sub)`，那就代表這個數字可以被塞進 `sub` 中
3. 若不符合 2.，代表回傳的值是**替換**的位置，就把 `sub` 中該位置換成現在的數字
### Code
```python!=
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
sub = []
for num in nums:
position = bisect.bisect_left(sub, num)
# current number is larger than all number in the sub array
if position == len(sub):
sub.append(num)
else:
# replace the sub[position] with current number
sub[position] = num
return len(sub)
```
如果不使用 `bisect`，自己寫
```python!=
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# Find the insertion point for target in arr to maintain sorted order
# find a position x, where it is the 1st position that arr[x] >= target
def binary_search_left(arr, target):
l, r = 0, len(arr)
while l < r:
m = l + (r - l) // 2
if arr[m] < target:
l = m + 1
else:
r = m
return l
sub = []
for num in nums:
position = binary_search_left(sub, num)
if position == len(sub):
sub.append(num)
else:
sub[position] = num
return len(sub)
```
### Time & Space complexity
- Time: O(n * log(n))
- n: 遍歷 nums
- log(n): 在 `sub` 中用 binary search 找目標位置，`sub` 最長長度為 n
- Space: O(n)
- 使用 `sub` 來儲存最長的嚴格遞增子序列，最長長度為 n
Sign in with Wallet
Connect another wallet