---
# System prepended metadata

title: '**Leetcode筆記(Longest Increasing Subsequence)**'
tags: [medium, dynamic programming, leetcode]

---

# **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://i.imgur.com/UVnQgnx.png)


**講解連結**
https://www.youtube.com/watch?v=cjWnW0hdF1Y
Provided by. NeetCode

###### tags: `dynamic programming` `medium` `leetcode`