Z先生的乳牛在環形圍廊上排成一圈，將每頭牛身上蓋上一個 0 到 255 之間的整數，表示這頭牛的「品質數」，數字越大，品質越好。 Z先生為展現他的智慧，對賣主定下一條古怪的約定：買主只能從圍廊上連續選出他所需的 M 頭乳牛。身為精明的買主，你當然希望選出的這隻 M 頭乳牛的「品質數」總和最大。
如：排成一圈的 5 頭乳牛的範例：10、3、9、7、1。
現在你需要買 2 頭乳牛。顯然選擇標號為 7 和 9 的兩頭乳牛「品質數」總和最大，為 16，是你的最佳的選擇。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入，每組測試資料的第一行是兩個數 N (1 <= N <= 10000) 和 M (1 <= M <= 5000)，N 表示圍廊中乳牛的數目，而 M 表示你打算購買的乳牛的數目，兩個數之間用空格隔開。 接下來的 N 行，每行有一個 0 到 255 的整數，以順時針或逆時針順序給出每頭乳牛的「品質數」。需要注意的是，第一頭乳牛與最後一頭乳牛在位置上是相鄰的。 | 對於每個輸入，請輸出一行，即你選出的連續的 M 頭乳牛的最大「品質數」總和。 |
| 5 2 10 3 9 7 1 | 16 |
解題思路
將品質數的前綴和紀錄下來，並且從頭到尾判斷目前位置到之後 M 個奶牛的品質數總和，如果有遇到需要尾銜接頭的情況，就先將目前已經有的品質數加起來，再來把剩下的從第一個位置開始加。
範例程式碼－ZeroJudge D164: 最佳選擇
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
while (cin >> N >> M) {
vector<int>prefix;
prefix.push_back(0);
int ans = -999;
for (int i = 1; i<=N; i++) {
int tmp;
cin >> tmp;
prefix.push_back(prefix[i-1]+tmp);
}
for (int i = 1; i<=N; i++) {
if (i + M - 1 <= N) {
const int calc = prefix[i+M-1] - prefix[i-1];
ans = max(ans, calc);
}
else {
int calc = prefix[N] - prefix[i-1];
const int left = M - (N-i+1);
calc += prefix[left] - prefix[0];
ans = max(ans, calc);
}
}
cout << ans << "\n";
}
}
//ZeroJudge D164
//Dr. SeanXD