CSES Problem Set — Maximum Subarray Sum 題解
===

題目
---
給一個整數陣列，你的任務是找到最大的非空連續子陣列總和。

### 輸入
- 第一行有一個整數 $n$。（$1 \le n \le 2 \cdot 10^5$）
- 第二行有 $n$ 個整數 $x_i$。（$-10^9 \le x_i \le 10^9$）

### 輸出
輸出最大的非空連續子陣列總和。

範例測資
---

Input:
8
-1 3 -2 5 3 -5 2 2

Output:
9

最大總和發生在連續子陣列 $(3, -2, 5, 3)$，總和為 $3 + (-2) + 5 + 3 = 9$。

想法：Kadane 算法
---
> 下面我們將「非空連續子陣列」簡稱為「子陣列」。

假設題目輸入的陣列為 $(x_i)_{i=0}^n$，令 $m$ 為最大的子陣列總和，又令 $c_k$ 為最大的 $x_k$ 結尾子陣列總和，也就是說
\begin{align*}
m &= \max\Bigr\{\sum_{i=a}^b x_i \Bigm| 1\le a \le b \le n\Bigl\},\\
c_k &= \max\Bigr\{\sum_{i=a}^k x_i \Bigm| 1\le a \le k\Bigl\}.
\end{align*} 那麼很直接地就可以看出 $m = \max\{c_b \mid 1 \le b \le n\}$。那麼 $c_k$ 怎麼求呢？

假設以 $x_k$ 結尾的子陣列中，有最大總和 $c_k$ 的是子陣列 $(x_a, \dots, x_k)$。

如果 $a < k$，那麼我們就會發現子陣列 $(x_a, \dots, x_{k-1})$ 同時也會是以 $x_{k-1}$ 結尾的子陣列中有最大總和的那個，換句話說，子陣列 $(x_a, \dots, x_{k-1})$ 的總和是 $c_{k-1}$。這不難驗證，因為若 $(x_b, \dots, x_{k-1})$ 有更大的總和，那麼 $(x_b, \dots, x_k)$ 的總和也將會比 $c_k$ 大而產生矛盾。於是我們有 $c_k = c_{k-1} + x_k$。

除此之外，還有一種可能情況是 $a = k$，也就是說以 $x_k$ 結尾的子陣列中有最大總和的是單元素的子陣列 $(x_k)$，而且 $c_k = x_k$。

所以我們就可以總結出 $c_k = \max(c_{k-1} + x_k, x_k)$。（令 $c_0 = 0$）

我們只要按照 $k=1$ 到 $k=n$ 的順序計算 $c_k$，並隨時記錄最大值 $m$ 就好。又因為 $c_k$ 的計算只依賴於 $c_{k-1}$ 與 $x_k$，這個演算法的時間複雜度是 $O(n)$、空間複雜度是 $O(1)$。

### 範例程式碼

#include <iostream>
using namespace std;

int main() {
    int n, x;
    int max_sum = -1e9;
    int curr_sum = 0;
    
    cin >> n;
    for (int k = 1; k <= n; k++) {
        cin >> x;
        curr_sum = max(curr_sum + x, x);
        max_sum = max(max_sum, curr_sum);
    }
    
    cout << max_sum;
}

---
回 [「CSES題解集」](https://hackmd.io/MpE3CP9eQUu20n3scMF5Fw?view)