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