#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;


int* find_max_crossing_subarray ( vector<int> &ci, unsigned low, unsigned mid, unsigned high); //函数返回数组的指针
int* find_maximum_subarray (vector<int> &ci, unsigned low,  unsigned high);

//函数返回数组的指针
//函数的功能为寻找横跨中点的最大子数组的小标和和，并组成一个数组返回
int* find_max_crossing_subarray ( vector<int> &ci, unsigned low, unsigned mid, unsigned high)  
{
	int *temp = new int[3];   //为防止局部变量内存被释放掉，采用动态分配内存
	int left_sum = -1000;
	int right_sum = -1000;
	int sum = 0;
	unsigned max_left = 0;
	unsigned max_right = 0;
	for (int i = mid; i >= 0 && i >= low ; --i)
	{
	     sum =  sum + ci[i];
		 if(sum > left_sum )
		 {
		     left_sum = sum;
			 max_left = i;
		 }
	}
	sum = 0;
	
	for (unsigned j = mid + 1; j <= high; ++j)
	{
	     sum =  sum + ci[j];
		 if(sum > right_sum )
		 {
		     right_sum = sum;
			 max_right = j;
		 }
	}
	
	temp[0] =  max_left;
	temp[1] =  max_right;
	temp[2] =  left_sum + right_sum;
	return temp;

 }

//函数返回数组的指针
//函数的功能为寻找一个数组的最大子数组的下标和和
int* find_maximum_subarray (vector<int> &ci, unsigned low,  unsigned high)
{
	int *temp_1 = new int[3];   //为防止局部变量内存被释放掉，采用动态分配内存
	if (low ==  high)
	{
	    temp_1[0] =  low;
		temp_1[1] =  high;
		temp_1[2] =  ci[low];
		return temp_1;
	}
	else
	{
		 int mid = (low + high) / 2;
		int *temp_left = new int[3];
		int *temp_right = new int[3];
		int *temp_cross = new int[3];
	    temp_left= find_maximum_subarray(ci, low,mid);
		temp_right= find_maximum_subarray(ci, mid+1,high);
		temp_cross= find_max_crossing_subarray ( ci, low,mid,high) ;
		if (temp_left[2] > temp_right[2] && temp_left[2] > temp_cross[2] )
		{
		return temp_left;
		}
		else
		{
		    if ( temp_right [2] > temp_left[2]  && temp_right[2] > temp_cross[2] )
			{
			     return temp_right;
			}
			else 
			{
			    return temp_cross;
			}
		}

	}
}

int main ()
{
   vector<int> ai;
    int num = 0;
    cout << "please enter the numbers that need to find the maximum subarray:" << endl;
    while (cin >> num )
        ai.push_back(num);

	int* maximum_subarray = find_maximum_subarray(ai,0,ai.size () - 1);
	cout << maximum_subarray[0] << "\t"
		    << maximum_subarray[1] << "\t"
			<< maximum_subarray[2] << "\t"
			<< endl;
	delete[] maximum_subarray;

  return 0;
}