어려움DP이분 탐색

최장 증가 부분 수열

정수 배열 nums가 주어져요. 원소의 순서는 유지하되 몇 개를 골라 만든 수열 중, 값이 앞에서 뒤로 엄격히 증가하는 가장 긴 것의 길이를 반환해요. 원소가 이어져 있을 필요는 없어요.

가장 단순한 풀이는 dp[i]를 'i번째로 끝나는 증가 수열의 최대 길이'로 두는 O(n²)이에요. 각 i마다 앞의 모든 j를 보고 nums[j] < nums[i]이면 dp[j] + 1로 늘려요.

여기서 한 걸음 더 나아가면, '길이별 마지막 값의 최소'를 배열로 관리하고 이분 탐색으로 자리를 찾아 O(n log n)까지 줄일 수 있어요.

예시

예시 1

입력: nums = [10, 9, 2, 5, 3, 7, 101, 18]
출력: 4
설명: [2, 3, 7, 101] 또는 [2, 5, 7, 18] 등 길이 4가 최장이에요.

예시 2

입력: nums = [0, 1, 0, 3, 2, 3]
출력: 4
설명: [0, 1, 2, 3]이 최장이에요.

제한 사항

0 ≤ nums.length ≤ 100,000
-10^9 ≤ nums[i] ≤ 10^9
'엄격히 증가'이므로 같은 값은 이어 쓸 수 없어요.

tails 배열을 두고 각 값마다 이분 탐색으로 그 값 이상인 첫 자리를 찾아 덮어써요. 그 자리가 배열 끝이면 길이를 늘린 거예요. 마지막에 tails의 길이가 최장 증가 부분 수열의 길이예요. (더 쉬운 O(n²) DP로 시작해도 좋아요.)

javascript
Copy code
function longestIncreasingSubseq(nums) {
  const tails = [];
  for (const n of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < n) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = n;
  }
  return tails.length;
}

이전 문제정수 삼각형

다음 문제격자 경로의 수

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.