Portfolio

문제

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

풀이

재영


/**
 * @param {number[]} nums
 * @return {number}
 */
const binarySearchLeftIndex = (nums, start, end, target) => {
  let mid = Math.floor((start + end) / 2);

  const now = nums[mid];

  if (start > end) return start;

  if (target <= now) {
    if (target === now) return mid;
    return binarySearchLeftIndex(nums, start, mid - 1, target);
  } else {
    return binarySearchLeftIndex(nums, mid + 1, end, target);
  }
};



const lengthOfLIS = (nums) => {
  const numsLength = nums.length;

  const dp = [];
  const indexDp = new Array(numsLength).fill(0);

  for (let i = 0; i < numsLength; i += 1) {
    const now = nums[i];

    if (!dp.length || now > dp[dp.length - 1]) {
      dp.push(now);
    } else {
      const nowIndex = binarySearchLeftIndex(dp, 0, dp.length - 1, now);
      dp[nowIndex] = now;
    }
  }

  return dp.length;
};

효성


var lengthOfLIS = function(nums) {
    let dp = [];
    const len = nums.length;
    
    dp[0] = 1;
    
    for(let i = 1; i < len; i++) {
        let val = 1
        for(let j = i - 1; j >= 0; j--) {
            if(nums[j] < nums[i] && val < dp[j] + 1) {
                val = dp[j] + 1;
            }
            dp[i] = val;
        }
    }
    
    return Math.max(...dp);
};

Longest Increasing Subsequence

문제

풀이