#include<iostream>
#include<vector>
using namespace std;
/*******************************************************************************************/
//  分治方法，利用递归的思想  
//  ugly_chen     2014.11.3  22:24
//说明：把数组分为两部分，右边部分和左边部分，要不就是右边部分和左边部分之和.
// ——————————————————————》时间： O(NlogN)
/********************************************************************************************/
int  find_max_cross_subArray(int a[], int left, int mid, int right)
{
	int left_sum = 0;
	int max_left_sum = 0;
	for (int i = mid; i >= left; i--)
	{
		left_sum += a[i];
		if (left_sum > max_left_sum)
		{
			max_left_sum = left_sum;
		}
			
	}

	int right_sum = 0;
	int max_right_sum = 0;
	for (int i = mid + 1; i <= right; i++)
	{
		right_sum += a[i];
		if (right_sum > max_right_sum)
		{
			max_right_sum = right_sum;
		}
	}

	return max_left_sum + max_right_sum;
}

int find_max_subArray(int a[], int left, int right)
{
	int left_sum, right_sum, cross_sum;
	if (left == right)
	{
		return a[left];
	}
	else
	{
		int mid = (left + right) / 2;
		left_sum = find_max_subArray(a, left,mid);
		right_sum = find_max_subArray(a, mid + 1, right);
		cross_sum = find_max_cross_subArray(a, left, mid, right);
	}

	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;  
	return cross_sum;
}
/*——————————————————————————————————————————————————————————————————————————————————————————*/
//方法二：最暴力的方法  这里使用vector数组    时间： O(N^3)
//introduction: 对每一个可能的组合求和，然后比较最大的和.
/*———————————————————————————————————————————————————————————————————————————————————————————*/
int find_max_array2(const vector<int> &a)
{
	int max_sum = 0;
	for (size_t i = 0; i < a.size(); i++)
	{
		for (auto j = i; j < a.size(); j++)
		{
			int this_sum = 0;
			for (auto k = i; k <= j; k++)
				this_sum += a[k];

			if (this_sum>max_sum)
				max_sum = this_sum;
		}
	}
	return max_sum;
}

/************************************************************************************************/
//方法三：对上面的算法进行简化(实际上是去掉上面的第二层循环)
//introduction：还是所有组合的和，，每一次循环求出取其中最大的和保存在max_sum中.
// ——————————————————————》时间： O(N^2)
/*************************************************************************************************/
int find_max_array3(const vector<int> &a)
{
	int max_sum = 0;
	for (size_t i = 0; i < a.size(); i++)
	{
		int this_sum = 0;
		for (auto j = i; j < a.size(); j++)
		{
			this_sum += a[j];

			if (this_sum>max_sum)
				max_sum = this_sum;
		}
	}

	return max_sum;
}

/*————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————*/
//方法四：对数组中的元素进行扫描，用this_sum记录扫描元素的和，从跟第一个元素开始扫描，this_sum不能小于0，如果小于0，那么
//this_sum从新记录扫描元素的和(这个时候this_sum置为0)，如果this_sum不为0，那么就和max_sum比较（大于max_sum那就把this_sum的
//值给max_sum，不大于就不变）意思就是扫描到的最大和保存在max_sum中。
// ——————————————————————》时间： O(N)
/*—————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————*/
int find_max_array4(const vector<int> &a)
{
	int max_sum = 0;
	int this_sum = 0;
	for (size_t i = 0; i < a.size(); i++)
	{
		this_sum += a[i];

		if (this_sum > max_sum)
			max_sum = this_sum;
		else if (this_sum < 0)
			this_sum = 0;
	}

	return max_sum;
}

int main()
{
	int a[] = { 9, 6, -7, 1, 8,-20, 5, 3, 4, 0, 2 };
	std::cout << find_max_subArray(a, 0, 10) << std::endl;
	
	vector<int> aVec = { 9, 6, -7, 1, 8, -20, 5, 3, 4, 0, 2 };

	std::cout << find_max_array2(aVec) << std::endl;

	std::cout << find_max_array3(aVec) << std::endl;

	std::cout << find_max_array4(aVec) << std::endl;

	return 0;
}

求最大子数组的和，算法导论只分治递归求解，暴力求解，记忆扫描方法。