문제

• 정수 리스트 nums
• 가장 긴 증가하는 subseq

풀이

• 전에 백준에서 많이 풀어본 dp
• subseq의 시작점과 끝점이 다양할 수 있음을 유의
• O(n**2)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lenNums = len(nums)
        dp = [1 for _ in range(lenNums)]

        
        for i in range(1, lenNums):
            for j in range(i):
                if nums[j] < nums[i] and dp[j] >= dp[i]:
                    dp[i] = dp[j]+1
        
        return max(dp)

결과