300. 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].

이건 도저히 뭔소린지 몰라서 검색해보니까 '부분 수열'이라고 한다.

최장 증가 부분 수열
https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

My Answer 1: Wrong Answer (27 / 54 test cases passed.)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        maxlength = 0
        for i in range(0, len(nums)):
            subsequence = [nums[i]]
            for j in range(i+1, len(nums)):
                if subsequence[-1] < nums[j]:
                    subsequence.append(nums[j])
            print(subsequence)
            maxlength = max(maxlength, len(subsequence))
        return maxlength

이중 for 문 써서 nums[i] 기준으로 subsequence 들을 만들어서 최댓값을 구하도록 했는데
[0,1,0,3,2,3] -> [0,1,2,3] 처럼 이어지지 않는 subsequence 가 답일 경우 안됨...ㅎ

Dynamic Programming

Solution 1: Runtime: 3920 ms - 28.80% / Memory Usage: 14.8 MB - 6.21%

class Solution:
    # Dynamic programming bottom up
    # TC: O(n**2) Two loop
    # SC: O(n) dp array of size n 
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [1] * 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)

nums[i] > nums[j] 면 dp[i] = max(dp[i], dp[j] + 1)
앞에 자신보다 작은 값의 개수만큼 dp 값에 +1 해주나보다

다른 솔루션들보다 DP 방식이 런타임은 별로여도 외우기도 좋고 걍 좋아보이네요..^^