53. 최대 부분 배열

이 문제는 주어진 정수 배열에서 가장 큰 합을 가지는 연속된 부분 배열을 찾고 그 합을 반환하는 것입니다. 이 문제를 해결하기 위해 사용하는 알고리즘은 "카데인 알고리즘(Kadane's Algorithm)"으로 알려져 있습니다. 이 알고리즘은 매우 효율적이며, 시간 복잡도가 O(n)입니다. 이제 이 알고리즘을 사용한 코드의 작동 방식을 단계별로 설명하겠습니다.

1. 알고리즘의 핵심 아이디어

카데인 알고리즘의 핵심은 현재 위치까지의 최대 부분합을 유지하면서 배열을 한 번만 순회하는 것입니다. 각 요소를 살펴보면서, 그 요소를 포함하는 부분 배열의 최대 합을 계산하고, 이를 전체 최대 합과 비교하여 갱신합니다.

2. 코드의 주요 로직 설명

function maxSubArray(nums: number[]): number {
    if (nums.length === 0) return 0; // 배열이 비어있다면 0을 반환
    let currentSum = nums[0]; // 현재까지의 연속 부분합 초기화
    let maxSum = nums[0];     // 전체 최대 부분합 초기화
    for (let i = 1; i < nums.length; i++) {
        // 현재 값 단독 vs 이전 누적합에 현재 값을 더한 것 중 더 큰 값을 선택
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 전체 최대값 갱신
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
};

3. 각 단계별 동작 과정

• 초기화 단계:

  • currentSum과 maxSum을 배열의 첫 번째 요소로 초기화합니다. 이는 부분 배열이 최소한 하나의 요소를 포함해야 하므로 첫 번째 요소를 시작점으로 설정하는 것입니다.

• 반복 단계:

  • 배열의 두 번째 요소부터 시작하여 끝까지 반복합니다.
  • currentSum을 계산할 때 두 가지 선택이 있습니다:
    1. 현재 요소 nums[i]를 새로운 시작점으로 삼아 부분합을 시작하는 경우.
    2. 이전의 currentSum에 현재 요소를 더하여 부분합을 이어가는 경우.
  • Math.max(nums[i], currentSum + nums[i])을 통해 위 두 가지 중 더 큰 값을 선택하여 currentSum을 갱신합니다.
  • maxSum은 현재까지의 currentSum 중 가장 큰 값을 유지합니다. Math.max(maxSum, currentSum)을 통해 갱신합니다.

4. 핵심 변수들의 역할

• currentSum: 현재 위치까지의 최대 연속 부분합을 나타냅니다. 이 값은 매 반복마다 갱신되며, 현재 요소를 포함하는 부분 배열의 최대 합을 계산합니다.
• maxSum: 전체 배열을 통틀어 가장 큰 연속 부분합을 저장합니다. 최종적으로 이 값이 반환됩니다.

5. 왜 이 방법이 효과적인지

이 방법은 배열을 한 번만 순회하면서 각 요소에서의 최대 부분합을 효율적으로 계산하기 때문에 매우 빠릅니다. 각 요소마다 두 가지 선택을 비교하여 최적의 부분합을 유지하므로, 모든 가능한 부분 배열을 고려하는 것보다 훨씬 효율적입니다. 이 알고리즘은 불필요한 계산을 줄이고, 필요한 경우에만 최대값을 갱신하기 때문에 최적의 성능을 보장합니다.

이렇게 해서 우리는 주어진 배열에서 가장 큰 합을 가지는 부분 배열의 합을 효율적으로 찾을 수 있습니다.