문제 설명

Maximum Subarray - LeetCode

주어진 정수 배열 nums에서 연속된 서브어레이(subarray) 중 합이 가장 큰 값을 찾는 문제입니다.

✅ 제약 조건

  • 1 ≤ nums.length ≤ 10⁵
  • -10⁴ ≤ nums[i] ≤ 10⁴
  • O(N) 이하의 시간 복잡도로 해결하는 것이 바람직

해설

1️⃣ 브루트포스 (O(N²)) → 비효율적

  • 모든 가능한 부분 배열을 확인하며 최대 합을 찾음
  • 시간 복잡도 O(N²) → 입력 크기가 크면 비효율적

2️⃣ 동적 계획법 (DP, O(N))

  • 점화식:
    • dp[i] = max(dp[i-1] + nums[i], nums[i])
    • 즉, 현재 값을 새로운 서브어레이로 시작할지, 기존 서브어레이에 추가할지를 결정
  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N) (배열 dp를 저장)

3️⃣ 카데인 알고리즘 (Kadane’s Algorithm, O(N)) [추천]

  • DP에서 배열 저장 없이 최적화한 방법
  • 현재 서브어레이 합이 음수라면 새로운 서브어레이 시작
  • 시간 복잡도: O(N)
  • 공간 복잡도: O(1) (배열 사용 없이 변수 2개만 사용)

코드 풀이

Python

1
2
3
4
5
6
7
8
9

def maxSubArray(nums):
    max_sum = nums[0]  # 최대 합
    current_sum = nums[0]  # 현재 부분 배열의 합

    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])  # 현재 값 포함 여부 결정
        max_sum = max(max_sum, current_sum)  # 최댓값 갱신

    return max_sum

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

var maxSubArray = function(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform