종만북 코드 4.10

---

출처 종만북(프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1)

알고리즘 시간복잡도에 대한 내용이 이어지다가
최대 연속 부분 구간 합을 구하는 알고리즘들에 대한 설명이 있었다

…
배열 [-7, 4, -3, 6, 3, -8, 3, 4]에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3]으로, 그 합은 10입니다.
…

이후 해당 문제를 O($N^3$)과 O($N^2$) 속도로 해결하는 알고리즘 뒤에 O($NlogN$) 속도로 해결하는 알고리즘에 대한 코드가 나왔는데

코드 4.10 최대 연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘

// A[lo..hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlogn)
int fastMaxSum(const vector<int>& A, int lo, int hi) {
  // 기저 사례: 구간의 길이가 1일 경우
  if(lo == hi) return A[lo];
  // 배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눈다.
  int mid = (lo + hi) / 2;
  // 두 부분에 모두 걸쳐 있는 최대 합 구간을 찾는다. 이 구간은
  // A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
  // A[i..mid] 형태를 갖는 최대 구간을 찾는다.
  int left = MIN, right = MIN, sum = 0;
  for(int i = mid; i >= lo; --i) {
    sum += A[i];
    left = max(left, sum);
  }
  // A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
  sum = 0;
  for(int j = mid+1; j <= hi; ++j) {
    sum += A[j];
    right = max(right, sum);
  }
  // 최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
  int single = max(fastMaxSum(A, lo, mid),
                   fastMaxSum(A, mid+1, hi));
  // 두 경우 중 최대치를 반환한다.
  return max(left + right, single);
}

중앙에서 시작, 각각 좌우로 더해가며 구한 최대 합을 합치면
현재 배열의 중심을 포함한 연속 구간의 최대 합이 나온다
이어서 현재 구간을 다시 반으로 나눠 이분 탐색하면
모든 원소를 중심으로 최대 합을 구할 수 있다
이 중 가장 큰 값을 반환하는 방식이었다

이 이후에 바로 동적 계획법을 활용한 시간복잡도 O(N)의 알고리즘이 나왔다

코드 4.11 최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘

// A[]의 연속된 부분 구간의 최대 합을 구한다. 시간복잡도: O(n)
int fastestMaxSum(const vector<int>& A) {
  int N = A.size(), ret = MIN, psum = 0;
  for(int i = 0; i < N; ++i) {
    psum = max(psum, 0) + A[i];
    ret = max(psum, ret);
  }
  return ret;
}

명확하고 군더기가 없었다

나였다면 이 문제를 dp로 보고 풀 수 있었을까
솔직히 조금 감동해버렸다

다음부터는 시간이 좀 더 들더라도 직접 먼저 풀어보고 비교해보는것도 좋을 것 같다