算法学习之最大子序列问题

最大子序列问题：

即在给定序列中寻找一子序列使其和在所有子序列中最大。

代码实现如下：

[cpp]
#include
#include
using namespace std;

const unsigned int N = 5;

int maxSubSum1(const vector & a)
{
int max_sum = 0;

int begin = 0;
int interval = 0;

for(unsigned int i = 0; i < a.size(); i++)
{
for(unsigned int j = i; j < a.size(); j++)
{
int this_sum = 0;

for(unsigned int k = i; k <= j; k++)
{
this_sum += a[k];
}
if(this_sum > max_sum)
{
max_sum = this_sum;
begin = i;
interval = j;
}
}
}

cout << "The biggest subarray is:" << endl;
for( ; begin <= interval; begin++)
{
cout << a[begin] << "\t";
}

return max_sum;
}

//
int maxSubSum2(const vector & a)
{
int max_sum = 0;

int begin = 0;
int interval = 0;

for(unsigned int i = 0; i < a.size(); i++)
{
int this_sum = 0;

for(unsigned int j = i; j < a.size(); j++)
{
this_sum += a[j];
if(this_sum > max_sum)
{
max_sum = this_sum;
begin = i;
interval = j;
}
}
}

cout << "The biggest subarray is:" << endl;
for( ; begin <= interval; begin++)
{
cout << a[begin] << "\t";
}

return max_sum;
}

//
int maxSubSum3(const vector & a)
{
int max_sum = 0;
int this_sum = 0;

unsigned int begin = 0;
unsigned int count = 0;

for(unsigned int j = 0; j < a.size(); j++)
{
this_sum += a[j];
count++;

if(this_sum >max_sum)
{
max_sum = this_sum;
begin = (j+1) - count;
} www.2cto.com
else if(this_sum < 0)
{
this_sum = 0;
count = 0;
}
}

cout << "The biggest subarray is:" << endl;
for(unsigned int i = begin; i < begin + count; i++)
{
cout << a[i] << "\t";
}
return max_sum;
}

int main()
{
vector array(N);

int sub_sum = 0;
// maxSubSum1(array);
cout << "Please input " << N <<" number to the array:" << endl;

for(unsigned int i = 0; i < N; i++)
{
cin >> array[i];
}

sub_sum = maxSubSum3(array);

cout << "\nThe biggest sum of the subarray is:" << endl;
cout << sub_sum << endl;
return 0;
}

代码中给出了三种不同的方法，第一种的时间复杂度为O(n^3)。第二种为O(n^2)。第三种为O(n)。