300. Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

 

DP 문제

 

2개의 for문을 써서 기존의 longest increasing sequence를 활용한다.

 

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        dp_arr = [ 1 for i in range(len(nums)) ]
        
        for j in range(0, len(nums), 1):
            
            for i in range(j+1, len(nums), 1):
                
                if nums[i] > nums[j]:
                    dp_arr[i] = max(dp_arr[i], dp_arr[j] + 1) 
                #print(nums[i], nums[j])
        print(dp_arr)
        
        return max(dp_arr)

 

 

https://www.youtube.com/watch?v=CE2b_-XfVDk