最大子段和问题

以下给出具体代码：

#include <bits/stdc++.h>
using namespace std;

int subSumMax(int a[], int left, int right) {
    if (left == right) {
        return a[left];
    }

    int mid = (right - left) / 2 + left;

    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        left_sum = max(left_sum, sum = sum + a[i]);
    }

    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        right_sum = max(right_sum, sum = sum + a[i]);
    }

    return max(max(subSumMax(a, left, mid), subSumMax(a, mid + 1, right)),
               left_sum + right_sum);
}

int main() {
    int a[] = {13, -3, -25, 20, -3,  -16, -23, 18,
               20, -7, 12,  -5, -22, 15,  -4,  7};
    cout << subSumMax(a, 0, 15);
    return 0;
}