배열의 최대 부분합 알고리즘 (Maximum subarray problem)

JavaScript Info를 보다가 오랜만에 알고리즘 문제를 만났는데 숫자 배열의 최대 부분합을 구하는 문제였습니다. (문제 보기)
이 문제는 $O(n^2)$의 느린 풀이법과 $O(n)$의 빠른 풀이법이 있는데, 그 풀이법에 대해 정리했습니다.

문제 보기

입력값은 arr = [1, -2, 3, 4, -9, 6] 같이 숫자로만 구성된 배열이라고 가정해봅시다.
우리가 해야 할 일은 인접한 요소의 총합이 최대인 arr의 부분 배열을 찾는 것입니다.
부분 배열 요소들의 합을 리턴하는 함수 getMaxSubSum(arr)를 작성해 봅시다.

예시:

getMaxSubSum([-1, 2, 3, -9]) == 5
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6

요소 전체가 음수라면 아무런 요소도 선택하지 않아야 최댓값이 됩니다(부분 배열은 빈 배열). 그리고 합은 0이 됩니다.

getMaxSubSum([-1, -2, -3]) = 0;

가능하다면 성능을 고려하여 답안을 작성해 봅시다. 답안은 $O(n^2)$ 또는 $O(n)$까지 가능합니다.

느린 풀이법

일단 brute-force하게 접근하면, 모든 연속된 부분합들 중 최대값을 찾는 방식으로 풀 수 있습니다.

function getMaxSubSum(arr) {
  // 최대값은 음수가 나올 수 없으니 0으로 초기화 해줍니다.
  // (음수를 포함한다면 -Infinity로 초기화 합니다.)
  let max = 0;
  
  for (let i = 0; i < arr.length; i++) {
    let sum = 0;
    for (let j = i; j < arr.length; j++) {
      // sum = i~j까지의 합
      sum += arr[j];
      // sum이 max보다 크면 max를 갱신
      if (max < sum) max = sum;
    }
  }
  
  return max;
}

이렇게 하면 시간 복잡도가 $O(n^2)$이 되기 때문에 배열이 길어질수록 수행시간이 급격하게 증가합니다.

빠른 풀이법

'최대 부분합 문제'는 전형적인 DP 문제입니다. 부분의 최적해를 통해 전체의 최적해를 구할 수 있기 때문입니다.

F(n)을 n번째 요소를 포함하는 가장 큰 부분합 이라고 한다면, F(n)은 다음과 같이 표현할 수 있습니다.
F(n) = { 이전 부분합에 n번째 요소를 포함 vs n번째 요소부터 새롭게 시작 }

이를 식으로 표현하면 다음과 같습니다.

$F_n = max(F_{n-1}+a_n, a_n)$

직접 문제를 풀면서 확인 해 봅시다.
배열 [-1, 2, 3, -9]이 있을 때 최대 부분합을 구하려고 합니다.

F(0) = -1
F(1) = max(-1+2, 2) = 2
F(2) = max(2+3, 3) = 5
F(3) = max(5-9, -9) = -4

i번째 요소를 포함한 최대 부분합을 구했기 때문에 이 중에 가장 큰 값인 5가 전체 배열에 대한 최대 부분합이 됩니다.

그러면 단순히 배열 F를 찾고, F 중에 최대값을 구하는 문제가 되었으니 다음과 같이 작성할 수 있습니다.

function getMaxSubSum(arr) {
  // 마찬가지로 최대값은 음수가 나올 수 없으니 모두 0으로 초기화 해줍니다.
  // (음수를 포함한다면 -Infinity로 초기화 합니다.)
  let max = 0;
  let partialMax = 0;
  
  for (let item of arr) {
    // M_i를 찾는다.
    partialMax = Math.max(partialMax + item, item);
    // M_i가 max보다 크면 max를 갱신한다.
    if (max < partialMax) max = partialMax;
  }

  return max;
}

테스트 샌드박스가 있으니 샌드박스를 이용하면 빠르게 위의 코드를 테스트 해 볼 수 있습니다.