📚 단일 패턴

300. Longest Increasing Subsequence

동적 계획법으로 각 위치의 부분 수열 길이를 갱신해 O(n^2) 시간에 LIS를 계산하기

Oct 2, 2025 — dynamic-programming

문제 설명

LeetCode 300. Longest Increasing Subsequence (opens in a new window)

풀이 아이디어

             1   2 3      4
nums = [10,9,2,5,3,7,101,18]

이런 문제는 어떻게 풀어야 할까 ?
- brute force 로 가능한가 ?
- backtrack 으로 가능한가 ?
- 수학적 귀납법이 적용되나 ?
  - (i-1)번째까지의 LIS 가 있다면 (i)번째 LIS 를 구할 수 있는가 ?
dp[i]는 (i)번째 숫자에서 가장 긴 increasing subsequence 의 길이를 의미

해결 전략

Dynamic Programming 프레임

구현

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

    // dp[i]: maximum increasing subsequence at i
    const dp = Array(N).fill(1);
    dp[0] = 1;
    let max = 1;

    for (let i = 1; i < N; i += 1) {
        for (let j = 0; j < i; j += 1) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(
                    dp[i],
                    dp[j] + 1
                )
                if (max < dp[i]) max = dp[i];
            }
        }
    }
    return max;
};