算法不归路之最大子序列（C++版）

#include<iostream>
using namespace std;
const int N = -1024;
int findMaxCrossingSubarray(int arr[], int low, int mid, int high){
    int leftSum = N, rightSum = N, sum = 0;

    for(int i = mid; i != low - 1; --i){
        sum = sum + arr[i];
        if(leftSum < sum){
            leftSum = sum;
        }
    }
    sum = 0;
    for(int  i = mid + 1; i != high + 1; ++i){
        sum = sum + arr[i];
        if(rightSum < sum){
            rightSum = sum;
        }
    }
    return (leftSum + rightSum);
}

int findMaxSubarray(int arr[], int low, int high){
    int left_sum, right_sum, cross_sum;
    if(low == high){
        return arr[low];
    }
    else{
        int mid = (low + high)/2;
        left_sum = findMaxSubarray(arr, low, mid);
        right_sum = findMaxSubarray(arr, mid+1, high);
        cross_sum = findMaxCrossingSubarray(arr,low,mid, high);
        if(left_sum >= right_sum && left_sum >= cross_sum)
        return left_sum;
        else if(right_sum >= left_sum && right_sum >= cross_sum)
            return right_sum;
        else
            return cross_sum;
    }
}

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