//典型分治思想，适合使用递归处理。我们可以考虑将给定的数组分成两部分，
//那么最大子数组必定存在于左侧部分，或者右侧部分，或者是跨越了分界线的部分。
//那么，只要分别求出这三种情况下的最大子数组，再进行比较，就能得出最后的结果。
#include<iostream>
#include<cstdlib>
using namespace std;
void find_max_crossing_subarray(int* arr, int low, int mid, int high, int& cross_low, int& cross_high, int& cross_sum)
{
    int sum = 0;
    int left_sum = arr[mid] - 1;
    for (int i = mid; i >= low; i--)
    {
        sum += arr[i];
        if (sum >= left_sum)
        {
            left_sum = sum;
            cross_low = i;
        }
    }
    sum = 0;
    int right_sum = arr[mid + 1] - 1;
    for (int i = mid + 1; i <= high; i++)
    {
        sum += arr[i];
        if (sum >= right_sum)
        {
            right_sum = sum;
            cross_high = i;
        }
    }
    cross_sum = left_sum + right_sum;
}
void find_max_subarray(int* arr, int low, int high, 
                       int& result_low, int& result_high, int& result_sum)
{
    if (low == high)
    {
        result_low = low;
        result_high = high;
        result_sum = arr[low];
        return;
    }
 
    int mid = (low + high) / 2;
 
    int left_low = 0;
    int left_high = 0;
    int left_sum = 0;
    find_max_subarray(arr, low, mid, left_low, left_high, left_sum);
 
    int right_low = 0;
    int right_high = 0;
    int right_sum = 0;
    find_max_subarray(arr, mid + 1, high, right_low, right_high, right_sum);
 
    int cross_low = 0;
    int cross_high = 0;
    int cross_sum = 0;
    find_max_crossing_subarray(arr, low, mid, high, cross_low, cross_high, cross_sum);
 
    if (left_sum >= right_sum && left_sum >= cross_sum)
    {
        result_low = left_low;
        result_high = left_high;
        result_sum = left_sum;
    }
    else if (right_sum >= left_sum && right_sum >= cross_sum)
    {
        result_low = right_low;
        result_high = right_high;
        result_sum = right_sum;
    }
    else
    {
        result_low = cross_low;
        result_high = cross_high;
        result_sum = cross_sum;
    }
}
int main()
{
    int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
	cout<<"17:";
	for(int i=0;i<=15;i++){
    cout<<A[i]<<",";
	}
	cout<<endl;

    int low = 0;
    int high = 0;
    int sum = 0;
    find_max_subarray(A, 0, 15, low, high, sum);
    cout<<"则最大子数组为："<< "{";
    for (int i = low; i <= high; i++)
    {
		cout << A[i] << ", ";
    }
    cout << "(sum = " << sum << ")" << "}" << endl;
	cout<<"输出左下标、右下标及最大值："<<"["<<low<<","<<high<<","<<sum<<"]"<<endl;
    system("pause");
    return 0;
}