[Leetcode] 300. Longest Increasing Subsequence 문제풀이

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

Longest Increasing Subsequence - LeetCode

 

문제 내용

배열에서 증가하는 수열중에 길이가 가장 큰 수열 찾기 문제

 

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.

 

문제 풀이

시작점을 고정해서 찾으면 O(n^2) 만큼 시간이 걸린다.

탐색하는 수 n개 이외에 증가하는 수를 찾는 부분을 줄일 필요가 있다.

 

DP와 바이너리 서치를 이용해서 풀었다.

 

증가하는 수 특징을 자세히 보면

 

같은 길이로 주어질 경우 값이 작은 것이 유리하다.

이유는 앞에 값이 작아야 더 길게 증가하는 수열을 구할 수 있다.

 

DP를 이용할때 모든 경우의 수를 다 기록하지 않고 겹치게 기록하면 된다.

가장 긴 부분만 구하면 되기 때문에

현재 lis 구한 배열의 중간에 삽입해도 작은 수로 대체되거나 늘어나서 상관없다.

 

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis;
        lis.push_back(nums[0]);
        
        for (int i = 1; i < nums.size(); ++i) {
            if (lis.back() < nums[i]) {
                lis.push_back(nums[i]);
            } else {
                int j = lower_bound(lis.begin(), lis.end(), nums[i]) - lis.begin();
                lis[j] = nums[i];
            }
        }
        
        return lis.size();
    }
};