[LeetCode] 300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

Medium

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

 

Constraints:

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

---

문제 풀이

문제 접근

1. 제한 조건이 10^4 * 2 이므로 시간복잡도는 N^2 까지 가능해보인다. 
2. 모든 값을 확인하면서 만들 수 있는 배열을 생성해야한다.
3. 주어진 리스트를 차례로 지나치면서, 기존의 추가된 정답 리스트의 값을 교체해준다.

풀이

1. 리스트의 처음 값을 정답 리스트에 추가한다.
2. 그 이후 값이 정답 리스트의 마지막 값보다 크다면 정답 리스트 마지막에 넣는다.
3. 반대로 그 값이 정답 리스트의 마지막 값보다 작다면 앞의 모든 숫자를 확인해봐야한다.
4. 정답 리스트의 앞쪽 숫자가 현재 숫자보다 작으면 그 자리의 숫자와 교체 해준다.
   1. 중간에 작은 숫자들을 교체해줘야 하는 이유는 새로운 숫자들의 집합이 이미 구해진 정답 집합보다 작을 수 있기 때문이다.
   2. 예시: [3,5,6,2,5,4,19,5,6,7,12]
      1. 숫자를 마지막에만 바꿨을때 정답: 3, 5, 6, 7, 12
      2. 앞의 모든 작은 수를 교체했을때 정답: 2, 4, 5, 6, 7, 12 // (3, 5, 6) -> (2, 5, 6) -> (2, 4, 6) -> (2, 4, 6, 19) -> (2, 4, 5, 19) -> (2, 4, 5, 6) ... (2, 4, 5, 6, 7, 12)
      3. (2, 4, 5, 19) 부분에서 앞의 숫자들이 모두 작아지는 것으로 교체가 됬기 때문에 19와 6을 교체할 수 있다.
5. 만들어진 정답 리스트의 길이를 리턴한다. 

소스코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = [nums[0]]
        for num in nums[1:]:
            if num > sub[-1]:
                sub.append(num)
            else:
                idx = 0
                while num > sub[idx]:
                    idx += 1
                sub[idx] = num
        return len(sub)