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

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

最大子序列问题：

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

代码实现如下：

#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;
        }
        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)。