Skip to content

📚 단일 패턴

53. Maximum Subarray

Kadane's Algorithm과 동적 프로그래밍을 사용하여 연속된 부분 배열의 최대 합 찾기

Sep 30, 2025 — dynamic-programming

문제 설명

LeetCode 53. Maximum Subarray (opens in a new window)

풀이 아이디어

sliding window 는 적용하기 어려움. window expand/shrink 시점을 정의하기 어려움.
Dynamic programming 적용.
dp[i] 는 nums[i] 까지의 최대 합을 의미.
Kadane’s Algorithm: dp[i] 는 dp[i-1] + nums[i] 와 nums[i] 중 큰 값을 선택.

구현

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

    const dp = Array(N).fill(0);
    dp[0] = nums[0];
    max = nums[0];

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

    return max;
};