d784: 一、連續元素的和

2021-06-02 23:17:06 +0800 CST Tags: dp, kadane, sequence

出處：https://zerojudge.tw/ShowProblem?problemid=d784
提交：https://zerojudge.tw/Submissions?problemid=d784&account=allllllan123456

問題：給定 $n\in[1,100]$ 個範圍為 $[-10000,10000]$ 的整數 arr[1:n]，試求最大的非空連續子序列和？

解法：這題有個很典型的解法稱為 Kadane’s algorithm [1]，裡面有非常易懂的證明，它本質上就是 DP，卻不像其他題目一樣需要隨時存取不同位置的值，只需要上一個位置而已，所以實作上不會宣告陣列。中心思想是這樣的，定義 dp[i] 為以 arr[i] 為結尾的最大連續子序列和，那麼這個序列要嘛只有自己，要嘛會包含前一個元素，但是有包含前一個元素的那個 case 我們一定會希望它自己也有最大的和，這樣跟自己這個元素拼起來才會最大，所以它的遞迴式可以寫成：dp[i] = max(dp[i-1] + arr[i], arr[i])，就如前面所說，dp[i] 只會用到 dp[i-1]，所以 dp[.] 其實只需要一個變數來記錄就可以了。那最後的答案其實就是 max(dp[1], dp[2], …, dp[n])。

附註：
[1] https://quanticdev.com/algorithms/dynamic-programming/kadanes-algorithm/

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int T; cin >> T;
 6    while (T--) {
 7        int sum=0, ans=INT_MIN, n; cin >> n;
 8        while (n--) {
 9            int a; cin >> a;
10            sum = max(sum + a, a);
11            if (sum > ans) ans = sum;
12        }
13        cout << ans << '\n';
14    }
15    return 0;
16}