300. Longest Increasing Subsequence

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

주어진 배열에서 가장 길게 증가하는 숫자의 수..?를 구하는 문제이다.

예를 들어
[1,2,4,3]가 있으면

->[1,2,3]이나 [1,2,4] 3개의 숫자 이므로 3을 반환한다.

만약에 맨 뒤에 3부터 탐색을 한다고 하면
]
자기 자신 한개 3, 그리고 4,3를 비교하면 4,3은 decreasing이므로 해당 X
[4]와 [2,4]를 비교하면 4<2,4
[2,4],[1,2,4]를 비교하면 1,2,4가 더 많기 떄문에 최종적으로 가장 큰 3을 lis에 넣어준다

이런식으로 탐색하며 가장 큰 값을 반환한다

시간복잡도는 o(n^2)이다

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lis = [1] * len(nums) 
        
        #[1,2,4,3]
        
        for i in range(len(nums)-1,-1,-1):
            for j in range(i+1,len(nums)):
                if nums[i]< nums[j]:
                    lis[i] = max(lis[i], 1+lis[j])
        return max(lis)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lis = [1] * len(nums) 

        #
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    lis[i] = max(lis[i], 1+lis[j]) 

    
        return max(lis)

22.12.01 복습