//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
*/
转载于:https://www.cnblogs.com/plxx/p/3232863.html
