[LeetCode] 300. Longest Increasing Subsequence

접근

• 다이나믹 프로그래밍을 활용하여 문제를 풀어야 함
• subsequence의 특징 중 앞의 원소에서 가능했던 갯수를 포함할 수 있다는 점을 캐치해야 함

 

문제 링크

https://leetcode.com/problems/longest-increasing-subsequence/description/

 

솔루션

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

        for i in range(nums_length):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)

        return max(dp)