基本思路

对于区间[l,r]内的最大子段和可以分为三种情况：
其中mid为区间[l,r]的中点，[i,j]为最大子段区间
1. i < j < mid
2. i < mid < j
3. i < j < mid

分治法

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;
int n;
int a[N];

int rec(int l, int r) {
    if (l == r) return a[r];

    int mid = l + r >> 1;

    int sum = 0, left = -INF, right = -INF;
    //求[l,mid]区间内的最大子段和
    for (int i = mid; i >= l; i--) {
        sum += a[i];
        left = max(left, sum);
    }
    sum = 0;
    //求[mid+1,r]区间内的最大子段和
    for (int i = mid + 1; i <= r; i++) {
        sum += a[i];
        right = max(right, sum);
    }

    return max(max(rec(l, mid), rec(mid + 1, r)), left + right);
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    cout << rec(0, n - 1) << endl;

    return 0;
}