CSES – Maximum Subarray Sum

題目連結

題意

給 n 個整數，找到最大的連續，非空的總和。(選的元素一定要連續)

解題方法

這題的解法需要用到一點動態規劃 (Dynamic Programming) 的概念，這也是一題非常經典的動態規劃題！

狀態

dp[i] 表示到位置i為止的 maximum subarray sum

轉移

dp[i] = max(a[i], dp[i-1] + a[i])
(選擇 dp[i-1] + a[i]代表從前面已經累積的最佳值加上現在的值，而選擇a[i]代表放棄前面的值從現在這格開始)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    long long ans = a[0];
    dp[0] = a[0];
    for(int i = 1;i < n;i++){
        dp[i] = max(a[i], a[i]+dp[i-1]);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}