算法學習之最大子序列問題

最大子序列問題：

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

代碼實現如下：

[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.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<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)。