Maximum Subarray Explanation

Problem Summary

Find the contiguous subarray with the largest sum.

Detailed Explanation

이 문제는 **카데인 알고리즘(Kadane's Algorithm)**으로 최대 부분 배열 합을 구하는 방법을 학습합니다. ## 핵심 개념: 카데인 알고리즘 현재 위치까지의 최대 합을 추적하며 배열을 순회합니다. ### 핵심 아이디어 각 위치에서 선택: 1. 현재 요소부터 새로 시작 2. 이전 합에 현재 요소 추가 ### 코드 분석 ```javascript let maxSum = arr[0]; let currentSum = arr[0]; for (let i = 1; i < arr.length; i++) { currentSum = Math.max(arr[i], currentSum + arr[i]); maxSum = Math.max(maxSum, currentSum); } ``` ### 시각화 ``` [-2, 1, -3, 4, -1, 2, 1, -5, 4] currentSum: -2 → 1 → -2 → 4 → 3 → 5 → 6 → 1 → 5 maxSum: -2 → 1 → 1 → 4 → 4 → 5 → 6 → 6 → 6 ``` ### 왜 O(n)인가? - 배열을 한 번만 순회 - 각 위치에서 O(1) 연산 - 브루트포스 O(n^3)보다 훨씬 효율적 카데인 알고리즘은 동적 프로그래밍의 대표적인 예입니다.

Solution Code

solution.js

function maxSubarray(arr) {
  let maxSum = arr[0];
  let currentSum = arr[0];
  for (let i = 1; i < arr.length; i++) {
    currentSum = Math.max(arr[i], currentSum + arr[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Key Concepts from This Problem

1. 카데인 알고리즘

2. 동적 프로그래밍

3. 최대 부분 합

4. 최적화

Common Mistakes

✗ maxSum과 currentSum을 첫 요소로 초기화해야 합니다

✗ 모든 요소가 음수일 때도 처리해야 합니다

✗ 빈 배열 처리를 고려해야 합니다

Hints

Hint 1: Kadane 알고리즘을 사용하세요.

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #동적프로그래밍 #Kadane