題目: 在一個數組中, 找出連續和最大的子序列.
使用兩個變量, 一個變量存儲當前值, 一個變量存儲最大值, 並設一個臨時數組, 用於更新最大和數組.
時間復雜度O(n).
代碼:
/*
* main.cpp
*
* Created on: 2014.9.19
* Author: spike
*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int FindSequence (int data[], int length, vector<int>& vi){
if (data == NULL || length <= 0)
return INT_MIN;
int greatest = INT_MIN;
int cur = 0;
vector<int> tmp;
for (int i=0; i<length; ++i) {
if (cur <= 0) {
cur = data[i];
tmp.clear();
tmp.push_back(data[i]);
} else {
cur += data[i];
tmp.push_back(data[i]);
}
if (cur > greatest) {
vi = tmp;
greatest = cur;
}
}
return greatest;
}
int main(void)
{
int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
int length = sizeof(data)/sizeof(data[0]);
vector<int> vi;
int g = FindSequence(data, length, vi);
cout << g << ": ";
for (size_t i=0; i<vi.size(); ++i) {
cout << vi[i] << " ";
}
cout << endl;
return 0;
}
輸出:
18: 3 10 -4 7 2