LeetCode 300 - Longest Increasing Subsequence (Medium)

문제

LeetCode - 300번

풀이 과정

가장 긴 부분수열을 구하는 LIS 문제입니다.
동적 계획법 을 이용해서 문제를 해결할 수도 있지만 이분 탐색 을 이용하면 Nlog(N) 의 시간 복잡도로 해결할 수 있습니다.

코드

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

  for (const num of nums) {
    if (memo.length === 0) {
      memo.push(num);
      continue;
    }

    if (memo.length > 0 && memo[memo.length - 1] < num) {
      memo.push(num);
    } else {
      const idx = binarySearch(memo, num);
      memo[idx] = num;
    }
  }

  return memo.length;
};

function binarySearch(arr, target) {
  let lo = 0,
    hi = arr.length - 1;
  let idx = 2e9;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);

    if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      idx = Math.min(idx, mid);
      hi = mid - 1;
    }
  }

  return idx;
}