算法学习之最大子序列问题
最大子序列问题:
即在给定序列中寻找一子序列使其和在所有子序列中最大。
代码实现如下:
[cpp]
#include <iostream>
#include <vector>
using namespace std;
const unsigned int N = 5;
int maxSubSum1(const vector<int> & 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<int> & 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<int> & 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.zzzyk.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<int> 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)。
补充:软件开发 , C++ ,