# Leetcode 300. Longest Increasing Subsequenece

## 題解

### 題解

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # Time complexity: O(n^2)
        # Space complexity: O(n)
        n = len(nums)
        dp = [1 for i in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)

### 貪心 + 二分搜索

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # Time complexity: O(nlogn)
        # Space complexity: O(n)
        lts = []

        for n in nums:
            if not lts or n > lts[-1]: # 如果lts沒有元素或者 n 大於遞增序列的最後一位
                lts.append(n)
            else:
                # 搜索要替換的位置
                left, right = 0, len(lts) - 1
                loc = right
                while left <= right:
                    mid = left + (right - left) // 2
                    if lts[mid] >= n:
                        loc = mid
                        right = mid - 1
                    else:
                        left = mid + 1
                lts[loc] = n
        return len(lts)