[PS] Leet | 300. 가장 긴 증가 수열

문제

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

조건

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

답

단조 증가하는 수열을 담을 리스트 incList를 새로 만들어 nums를 탐색합니다.

 

nums의 각 항목들 num을 증가 수열로 재배열하게 되는데, 이 과정에서 incList에 대한 이진탐색으로 num이 들어갈 위치를 찾을 수 있습니다.

문제에서 구하고자 하는 것은 단조 증가하는 하위 수열 자체가 아닌 하위 수열의 길이입니다.

 

따라서, 새로운 최댓값이 등장하는 경우에만 incList의 끝에 새로 추가하고, 다른 경우라면 이진탐색으로 찾은 위치에 있던 요소를 대체합니다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    incList = [];

    const binSearch = (lst, item, left, right) => {
        if (lst.length === 0) {
            return 0;
        }

        if (left === right){
            return (item <= lst[left])? left : left + 1;
        }
        const mid = Math.floor((left + right) / 2);

        const idxLeft = binSearch(lst, item, left, mid);
        const idxRight = binSearch(lst, item, mid + 1, right);

        return (idxLeft <= mid)? idxLeft : idxRight;
    }

    for (const num of nums) {
        const idx = binSearch(incList, num, 0, incList.length-1);

        if (idx === incList.length) {
            incList.push(num);
        } else {
            incList[idx] = num;
        }
    }

    return incList.length;
};