題目敘述：https://zerojudge.tw/ShowProblem?problemid=d784
解題想法：DP, maximum subarray
- 數列問題變化很多，先觀察其覆現性(recurrence)。
- 讀入測資，順便加總，並紀錄出現過的最大和 (mx)。當目前累計和 (now) 變成負值時，就將其重置為零，因其對後續的結果沒有貢獻。
- 答案可能是負數，所以 mx 的初始值設為 -INF。
#include <iostream>
using namespace std;
int main() {
int n, m, mx, now, tmp;
while (cin >> n){
while (n--){
cin >> m;
mx = -10000;
now = 0;
for (int i = 0; i < m; i++){
cin >> tmp;
now += tmp;
mx = max(mx, now);
if (now < 0) now = 0;
}
cout << mx << "\n";
}
}
}
Python 程式碼 (credit: Amy Chou)
T = int(input())
for Case in range(T):
N = list(map(int, input().split()))
N.pop(0)
Sum = 0
mx = -1e9
for n in N:
Sum += n
if (Sum > mx): mx = Sum
if (Sum < 0): Sum = 0
print(mx)