[dp]300. Longest Increasing Subsequence [python]

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

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

 

한줄요약  증가하는 수열 중에 최대 갯수

 

DP 랑 binary search  로 풀 수 있다. 

 

DP로 푼다면, 

1) 10, 9, 2, 5 순으로 방문할때,  방문한 숫자를 포함할때의 최댓값을 넣으면서 진행한다. 

1번째 for문은 nums를 순회하는데 이용하고, 

2번째 for문은 현재 숫자를 포함하기 위해서 이전에 방문했던 값들 중에 고를 수 있는 값중 최댓값을 고른다. 

조건1) 따라서 고를수있는 ( = 증가하는 수열이므로, 현재값 보다 작은), 

조건2) 최댓값을 고른다. 

를 구현하면된다. 

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