【算法】分而治之(DivideAndConquer) -- C++源代码（VS2015）

#include <iostream>
using namespace std;

int Max3(int A, int B, int C)
{
    return A > B ? (A > C ? A : C) : (B > C ? B : C);
}

int DivideAndConquer(int arr[], int left, int right)
{
    if (left == right)
    {
        return arr[left];
    }
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBoardSum, MaxRightBoardSum;
    int LeftBoardSum, RightBoardSum;
    int i, center;

    center = left + (right - left) / 2;
    MaxLeftSum = DivideAndConquer(arr, left, center);
    MaxRightSum = DivideAndConquer(arr, center + 1, right);

    MaxLeftBoardSum = arr[center];
    LeftBoardSum = 0;
    for (i = center; i >= left; i--)
    {
        LeftBoardSum += arr[i];
        if (LeftBoardSum > MaxLeftBoardSum)
        {
            MaxLeftBoardSum = LeftBoardSum;
        }
    }

    MaxRightBoardSum = arr[center+1];
    RightBoardSum = 0;
    for (i = center + 1; i <= right; i++)
    {
        RightBoardSum += arr[i];
        if (RightBoardSum > MaxRightBoardSum)
        {
            MaxRightBoardSum = RightBoardSum;
        }
    }

    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBoardSum + MaxRightBoardSum);
}

int main()
{
    int arr[10] = { 11,-2,-3,-4,-5,-20,-4,-10,10,10 };
    cout << "max value is " << DivideAndConquer(arr, 0,9) << endl;

    system("pause");
    return 0;
}