[leetcode 300] Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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.

 

풀이:

-lower bound 사용

- dp는 가장 긴 수열을 저장하는 배열이다. (오름차순)

-  nums[i]를 dp의 마지막 숫자와 비교해서 nums[i]가 크면 dp에 집어 넣는다.

- 작다면 dp배열에서 nums[i] 이상의 숫자의 위치를 찾는다. -> lower bound 사용

 

 

lower_bound

- #include <algorithm>

- lower_bound(arr, arr+n, val) - arr 해야 idx를 return한다. 아니면 iterator itr가 리턴..

using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        int dp[n];
        memset(dp,0,sizeof(dp));
        
        dp[0] = nums[0];
        int size = 1;
        for(int i=1; i<nums.size(); i++){
            if(dp[size-1] <nums[i]){
                dp[size++] = nums[i];
            }else {
                int lb= (int)(lower_bound(dp, dp + size, nums[i]) - dp);
                dp[lb] = nums[i];
            }
        }
        return size;
    }
};