[LeetCode] 300 | Longest Increasing Subsequence | Python

---

문제 링크: https://leetcode.com/problems/longest-increasing-subsequence/

---

문제

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

---

조건

• 1 <= nums.length <= 2500
• $-10^4$ <= nums[i] <= $10^4$

---

내 풀이

nums=[2, 1, 5, 3, 4]라는 리스트가 있다고 하자.

각 자리별로 스스로만 포함한 increasing subsequence를 가질 수 있기 때문에 ans=[1, 1, 1, 1, 1]로 시작한다.

 

ans[0]에 대하여 ans[0] 앞에는 원소가 없으므로 ans[0]은 그대로 0이다.

 

ans[1]에 대하여 ans[1]보다 작은 원소가 앞에 없으므로 ans[1]은 그대로 1이다.

 

ans[2]에 대하여 ans[2]보다 작은 원소는 nums[0], nums[1]이므로, ans[2]는 ans[0], ans[1]중 큰 수+1이 된다.

 

이와 같은 방법을 계속 반복한 후, ans중 제일 큰 값을 리턴하면 된다.

---

코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        ans = [1] * N
        
        for i in range(1, N):
            maxi = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    maxi = max(maxi, ans[j])
                    
            ans[i] = maxi + 1
        
        return max(ans)