/*
最大子数组：一个数组中连续和最大的子数组。

用分治法解决最大子数组问题的基本思想：
把数组分成两段——left、right。则需要解决的问题变为求left的最大子数组、right的最大子数组以及
cross过中点的最大子数组，比较这三种取最大的即为结果。

*/
#include<iostream>
#define INF -100000

using namespace std;

struct set
{
    int max_left, max_right, sum;//最左坐标，最右坐标，左右之和
};

//解决，合并
set FIND_MAX_CROSSING_SUBRY(int a[], int low, int mid, int high)//寻找穿过中点的最大子数组
{
    set res;
    int left_sum = INF, sum = 0, right_sum = INF, i, j;

    for (i = mid; i >= low; i--)//从中点向左找最大和子数组
    {
        sum += a[i];
        if (sum > left_sum)
        {
            left_sum = sum;
            res.max_left = i;
        }
    }
    sum = 0;
    for (i = mid + 1; i <= high; i++)//从中点向右找最大和子数组
    {
        sum += a[i];
        if (sum > right_sum)
        {
            right_sum = sum;
            res.max_right = i;
        }
    }
    res.sum = left_sum + right_sum;

    return res;
}

//分解
set FIND_MAX_SUBRY(int a[], int low, int high)
{
    set left_ans, right_ans, cross_ans, ans;
    if (high == low)
    {
        ans.max_left = low;
        ans.max_right = high;
        ans.sum = a[low];
        return ans;
    }
    int mid = (low + high) >> 1;
    left_ans = FIND_MAX_SUBRY(a, low, mid);
    right_ans = FIND_MAX_SUBRY(a, mid + 1, high);
    cross_ans = FIND_MAX_CROSSING_SUBRY(a, low, mid, high);

    if (left_ans.sum >= right_ans.sum&&left_ans.sum >= cross_ans.sum)return left_ans;
    else if (right_ans.sum >= left_ans.sum&&right_ans.sum >= cross_ans.sum)return right_ans;
    else return cross_ans;
}

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

    set ans = FIND_MAX_SUBRY(a, 0, 15);

    cout << ans.max_left << " " << ans.max_right << " " << ans.sum << endl;

    system("pause");
    return 0;
}