輸入為 N＊M 大小的的陣列，每一格是一個介於 -100 與 100 之間的整數，表示經過這格可以累積的經驗值。
你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。
過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。
請你算出最多可以獲得的經驗值總和 (可能是負數)。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有兩個正整數 N 和 M (1 <= N <= 50，1 <= M <= 10000)。 接下來 N 行，每行包含 M 個整數。第 i 行的第 j 個數字表示在 (i, j) 位置可以得到的經驗值。 | 輸出可以獲得的最多經驗值總和。 |
| 1 5 2 1 4 -7 4 | 7 |
解題思路
將資料收到一個二維陣列「v」中，並且再宣告三個二維陣列，分別為「答案、左前綴合、右前綴合」。收完資料之後特別判斷第一行的左右前綴合，需要注意的是進行前綴合運算時，如果有發生前面都是負數的情況，這樣就對造成數值不正確，所以相加前綴和時需要宣告一個 sum 變數並且預設為 v[0][0]，將 sum = max(0, sum) + v[0][i]。這樣子的話就是判斷前面的前綴合是否是負數，並且將較大值加到前綴合中。將第一行的「答案」設定為該位置的左右前綴合較大者。
跑一個 For迴圈 從 1 到 N-1 (不包含第 0 行，剛剛有進行判斷了)，並且判斷其左右前綴合。這次比較不一樣的是還需要考慮從上一行往下走到目前這一行的情況。如果進行判斷時跑到邊界 (即第一個或最後一個位置)，則將這個位置的前綴合設定為「上一行該位置的答案」+「v[i][j]」，否則將這個位置的前綴合設定為 max(前一個位置的前綴合, 上一行該位置的答案 + v[i][j]。
輸出時輸出「答案陣列」最後一行的「最大值」。
範例程式碼－ZeroJudge F314: 勇者修煉
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<vector<int>>v, ans, lprefix, rprefix;
vector<int> l1prefix() {
int sum = v[0][0];
vector<int>l;
l.push_back(sum);
for (int i = 1; i<M; i++) {
sum = max(0 , sum) + v[0][i];
l.push_back(sum);
}
return l;
}
vector<int> r1prefix() {
int sum = v[0][M-1];
vector<int>r;
r.push_back(sum);
for (int i = M-2; i>=0; i--) {
sum = max(0 , sum) + v[0][i];
r.push_back(sum);
}
reverse(r.begin(), r.end());
return r;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i<N; i++) {
vector<int>hi, qq;
int sum = 0;
for (int j = 0; j<M; j++) {
int tmp;
cin >> tmp;
hi.push_back(tmp);
qq.push_back(0);
sum += tmp;
}
lprefix.push_back(qq);
rprefix.push_back(qq);
ans.push_back(qq);
v.push_back(hi);
}
const vector<int> l = l1prefix(), r = r1prefix();
for (int i = 0; i<M; i++) ans[0][i] = max(l[i], r[i]);
for (int i = 1; i<N; i++) {
for (int j = 0; j<M; j++) {
if (j == 0) lprefix[i][j] = ans[i-1][j] + v[i][j];
else lprefix[i][j] = max(lprefix[i][j-1], ans[i-1][j]) + v[i][j];
}
for (int j = M-1; j>=0; j--) {
if (j == M-1) rprefix[i][j] = ans[i-1][j] + v[i][j];
else rprefix[i][j] = max(rprefix[i][j+1], ans[i-1][j]) + v[i][j];
ans[i][j] = max(lprefix[i][j], rprefix[i][j]);
}
}
cout << *max_element(ans[N-1].begin(), ans[N-1].end()) << "\n";
}
//ZeroJudge F314
//Dr. SeanXD