最大子序列问题:
即在给定序列中寻找一子序列使其和在所有子序列中最大。
代码实现如下:
[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;
}
}
}