【分而治之】最大子陣列和

給定一個 10 個元素的陣列，請找出最大的連續子陣列和，所有子陣列加總會在 -1e8 到 1e8 之間。
輸入：1 2 3 4 5 -10 20 30 -40 10
輸出：55

#include <iostream>
using namespace std;

int divide(int L, int R);
int conquer(int L, int M, int R);

int a[10+5];

int main(){
    for(int i=0; i<10; i++)
        cin >> a[i];
    cout << divide(0, 9) << '\n';
}

int divide(int L, int R){
    if(L == R) return a[L];
    int maxL, maxR, maxLR, M=(L+R)/2;
    maxL = divide(L, M);
    maxR = divide(M+1, R);
    maxLR = conquer(L, M, R);
    return max(maxL, max(maxR, maxLR));
}

int conquer(int L, int M, int R){
    int sumL=0, sumR=0, maxL=-1e8, maxR=-1e8;
    for(int i=L; i<=M; i++){
        sumL += a[i];
        if(sumL > maxL) maxL = sumL;
    }
    for(int i=M+1; i<=R; i++){
        sumR += a[i];
        if(sumR > maxR) maxR = sumR;
    }
    return max(maxL, max(maxR, maxL+maxR));
}