Longest Increasing Subsequence

3337 단어 TILleetcodeTIL


문제

  • 정수 리스트 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)

결과

좋은 웹페이지 즐겨찾기