題目
1007 Maximum Subsequence Sum (25分)
Given a sequence of K integers { N1, N2, ..., N**K }. A continuous subsequence is defined to be { N**i, N**i+1, ..., N**j } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
了解與算法
經典的最大子序列和的問題，不過要多求兩個值：最大子序列的始末值，相當于要求出子序列的位置！
最右側的值很容易給出，因為每一次更新最大值時都會更新這個值，不需要考慮太多。
問題在于怎麼找到起始值？
這裡我想了很多，後來覺得是多慮了！隻需要抓住一個點就行：
當之前的子序列不可能是最大子序列的時候，更新起始值的下标(
temp_index
)！那麼我們怎麼知道這個子序列不可能是最大子序列呢？它的和小于零，出現這個特征不管後面是多大的值，隻要加上前面一部分，就會比不加上這一部分要小，是以我們應該直接舍棄，進入下一個子序列的搜尋！于是我們可以把下一個搜尋的起始下标設定為
i+1
，這裡的i為疊代變量！
因為這兩個下标的更新時間點是互斥的，不可能同時更新，是以要用
else if
連接配接，否則會導緻錯誤輸出！
代碼實作
#include <iostream>
#include <vector>
using namespace std;
int main() {
int count;
cin >> count;
vector<int> v(count);
// 最大值預設為-1，友善後面判斷有沒有找到最大值
// 左右下标初始值為整個數組的左右下标！
int max = -1, temp_max = 0, temp_index = 0, left = 0, right = count - 1;
for (int i = 0; i < count; ++i) {
cin >> v[i];
temp_max += v[i];
// 如果和已經小于零了，那麼再往下走肯定不會是最大子序列！
if (temp_max < 0) {
// 重置臨時最大值變量
temp_max = 0;
// 然後将下标移動到下一個值
temp_index = i + 1;
} else if (temp_max > max) {
// 如果找到了一個更大的和，就記錄這個最大值和左右下标，因為起伏不定是以左下标會一直變化，就使用temp_index來作為下标
max = temp_max;
left = temp_index;
right = i;
}
}
// 如果最大值小于0，那麼說明沒找到大于0的最大值，就将其置為0！
if (max < 0) max = 0;
cout << max << " " << v[left] << " " << v[right];
return 0;
}