[LeetCode] 300 | Longest Increasing Subsequence

300 | Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/

 

 

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:

 

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

 

Example 2:

 

Input: nums = [0,1,0,3,2,3]
Output: 4

 

Example 3:

 

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

 

 

 

정답 코드

 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1] * n

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

 

• dp로 풀이
• nums[i] > nums[j] 라면 (i가 j보다 오른쪽에 있음) dp[i] 와 1 + dp[j] 를 비교하여 max 값 갱신 !
• dp[j] 는 dp[i] 보다 왼쪽에 있기 때문에 저장 끝난 상태!