題意#
題目給定長度為 \( n \) 的整數陣列。
我們需要從中找出一條連續的子陣列（Subarray），使其數字總和「最大」。
陣列可能包含負數，且必須選出至少包含一個數字的子陣列。最後要求出這個最大總和。
思路#
這是經典的「最大子陣列和問題（Maximum Subarray Sum）」，可透過 Kadane’s Algorithm 高效求解。
從左到右掃描陣列，並使用 sum 記錄當前累積的子陣列和，隨時更新歷史最大紀錄 mx。
當累積總和 sum 變成「負數」時，代表這段子陣列會拖累後續數字的總和。
此時應將 sum 歸零，從下一個數字重新開始累積。
藉由「邊加邊記錄，小於零即歸零重來」的貪婪策略，只需線性掃描一次即可求得最大子陣列和。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
// sum 用來記錄當前累積的子陣列和，mx 用來記錄出現過的歷史最大值
int n, i, sum = 0, mx = -1e9;
cin >> n;
while (n--) {
cin >> i;
// 將當前的數字加入累積總和
sum += i;
// 隨時更新歷史最大紀錄
mx = max(mx, sum);
// 如果當前累積總和變成負數，代表這段子陣列只會拖累後面的數字
// 果斷將總和歸零，從下一個數字開始重新計算（Kadane's Algorithm 核心精髓）
if (sum < 0) sum = 0;
}
// 輸出歷史最大子陣列和
cout << mx;
}
