# **Leetcode筆記(Longest Increasing Subsequence)**
:::info
:information_source: 題目 : Longest Increasing Subsequence, 類型 : dynamic programming , 等級 : medium
日期 : 2023/02/ ,2023/06/13，2023/07/20，2023/12/05，2024/03/28，2024/10/20
:::
### 嘗試
想要用twoPointer法，希望用for迴圈去試每個數字，並且設定l與r通過狀況，時間複雜度O(n)，
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
extralength = 0
length = 1
for i in range(len(nums)-1):
l = i+1
r = len(nums) - 1
if nums[l] < nums[r] and nums[i] < nums[l]:
length = 3
extralength += 1
if nums[l] > nums[l-1]:
l += 1
else:
l += 2
if nums[r-1] > nums[r]:
r += 1
else:
r += 2
return length + extralength
```
2023/06/13
dp[i]的意義為 到i這個數字為止 最長的遞增數列
假設dp[1]到dp[i-1]都已經求得，該如何知道dp[i]為何?
那就往前面一個一個比，假設數列為a，那麼就把a[i]拿去和前面幾個a[1] ~ a[i-1]比較，若a[i]大於a[1]，那代表是一個遞增數列，那就可以更新dp[i] = max(dp[i], dp[1] + 1)
狀態方程式為
```python
dp[1] = 1
dp[i] = max(dp[i], dp[j] + 1)，j為比較對象
```
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
for i in range(len(nums)):
incre = 1
for j in range(i):
if nums[i] > nums[j]: # 代表是遞增
incre = max(incre, dp[j] + 1)
dp[i] = incre
return max(dp)
```
2023/07/19
既然是要找遞增，那必定是要跟**前面的"所有"數字**做比較，如果前面數字比較小，就可以加1，加入這個遞增序列
如果沒有找到，那就維持1
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
# 原始想法 :
# 如果後面比較大 : 加1
# 如果後面比較小 : 往前找到第一個比後面小的前面(可以找1 ~ i - 1)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 最大的不一定是最後一個(可能最後有極小值)
```
2023/12/05
```python
"""
nums = [10,9,2,5,3,7,101,18]
stack = [1,1,1,2,2,3,4,4]
hashmap = 0 : [0, 1] / 1 : [1, 2] / 2 : [0, 1] / 3 : [3, 3] / 4 : [2, 3] / 5 : [3, 4]
nums = [0,1,0,3,2,3]
stack = [1,2,1,3,3,4]
dp = []
"""
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[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
2024/03/28
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# dict, n : length -> 不能是n 沒有唯一性 / key要為index
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)
```
2024/10/20
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(0, i + 1):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
複雜度為O(nlogn)，binary search 為 round up(回傳l)，希望找到的是res中，比自己大一點的那個數字的index，把它替代成當前數字(較小)時，之後會更有機會找到更長的sequence(greedy)
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
res = []
for i, n in enumerate(nums):
# binary search
ind = self.binary_search_round_up(res, n)
if ind == len(res): # n is larger than any number
res.append(n)
else: # want to replace that large number
# so that in the future we can find a smaller number
res[ind] = n
return len(res)
def binary_search_round_up(self, res, n):
# to find the index of smallest number that is larger than n
# ex. res = [2, 3, 5], n = 4
# give back index = 2
l, r = 0, len(res) - 1
while l <= r:
mid = (l + r) // 2
if n < res[mid]:
r = mid - 1
elif n > res[mid]:
l = mid + 1
else:
return mid
return l
```
---
### **優化**
從list最後面開始找，把後面的數據丟給前面，時間複雜度O(n^2)，空間複雜度O(n)
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
LIS = [1] * len(nums) # 初始化為1 也就是只能走自己
for i in reversed(range(len(nums) - 1)): # 最後一個不用試
for j in range(i+1, len(nums)):
if nums[i] < nums[j]:
LIS[i] = max(LIS[i], 1 + LIS[j]) # LIS[i]初始為0 但有更好的就會更新
return max(LIS)
```
---
**:warning: 錯誤語法**
:::warning
LIS[i] = max(LIS[i], 1 + LIS[j])因為要更新自己
len((nums) - 1)要減1，最後一個數直接初始化在list
:::
**:thumbsup:學習**
:::success
Subsequence : 可刪一些element，但不能改變順序
max(list)返回list中最大數
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=cjWnW0hdF1Y
Provided by. NeetCode
###### tags: `dynamic programming` `medium` `leetcode`
Sign in with Wallet
Connect another wallet