최대 연속 부분 구간 합[c++]

// 최대 연속 부분 구간 합 문제
// [-7, 4, -3 ,6, 3 ,-8, 3, 4]의 최대 구간 합은 idx1 ~ idx4 즉, 10이다.
// 분할 정복과 동적계획법 두 가지 풀이
// 6 -1 -2 -3 3 4 일 경우 idx0 ~ idx5와 idx4 ~ idx5의 구간 합이 같지만 더 짧은 길이 구간을 반환할 것
// 입력 예 6 \n 6 -1 -2 -3 3 4 (크기6 값6개)
//         7 \n -7 4 -3 6 3 -8 3 4
// 출력 예 7 (maxSum)
//         10

#include <iostream>
#include <vector>

int MIN = 0;

using namespace std;

// 동적계획법 O(n)
// a[i]를 오른쪽 끝으로 갖는 최대합구간을 maxAt(i)라고 하면
// maxAt(i) = max(0, maxAt(i - 1) + a[i]
int dpMaxSum(const vector<int>& a) {
int maxSum = MIN;
int psum = 0;

for (int i = 0; i < a.size(); i++) {
psum = max(0, psum) + a[i];
maxSum = max(maxSum, psum);
}

return maxSum;
}

// 분할 정복 O(NlogN)
// left는 left의 오른쪽부터, right는 right의 왼쪽부터 구간 합 구하기
int divideAndConquerMaxSum(const vector<int>& a, int left, int right) {
// base: left와 right가 같을때 (길이 1)
if (left == right) return a[left];

int mid = (left + right) / 2;
int leftMaxSum = MIN, rightMaxSum = MIN, sum = 0;

// left ~ mid 구간에서 오른쪽부터 합
for (int i = mid; i >= left; i--) {
sum += a[i];
leftMaxSum = max(leftMaxSum, sum);
}

// mid+1 ~ right 구간에서 왼쪽부터 합
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += a[i];
rightMaxSum = max(rightMaxSum, sum);
}

// left 구간 또는 right 구간에서 만의 구간합이 최대 값일 경우
int single = max(divideAndConquerMaxSum(a, left, mid), divideAndConquerMaxSum(a, mid + 1, right));
// left 구간과 right구간이 이어진 곳에서 구간합의 최대 값이 발생할 경우
int connect = leftMaxSum + rightMaxSum;

return max(single, connect);
}



int main() {
int n;
cin >> n;

vector<int> array;
int a;
for (int i = 0; i < n; i++) {
cin >> a;
array.push_back(a);
}

cout << "동적 계획법 결과 : " << dpMaxSum(array) << endl;
cout << "분할 정복 결과 : " << divideAndConquerMaxSum(array, 0, n - 1) << endl;

return 0;
}