和最大的子序列之一

//o(n*n)
【暴力搜索】
再一个数列中，查找一个连续子数列，使该连续子数列的和最大。
依次以序列的每一个数为子数列的开头，遍历所有的情况，时间复杂度为o(n*n)。


#include<iostream>
using namespace std;
void MaxSubSet_1(int nums[], int length)
{
	if (length == 0)
		return;

	int start = 0;
	int end = 0;
	int maxSum = nums[0];
	int sum;
	
	for (int i = 0; i < length; i++)
	{
		sum = 0;
		for (int j = i; j < length; j++)
		{
			sum +=nums[j];
			if (sum > maxSum)
			{
				start = i;
				end = j;
				maxSum = sum;
			}
		}
	}

	cout << "Max:" << maxSum << " ( " << start << ", " << end << " )" << endl;
}
int main()
{
	int A[] = {0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5};
	MaxSubSet_1(A,13);
	return 0;
}
/*

  结果：
  Max:43 ( 5, 12 )
Press any key to continue


*/