# AP325 P-4-13. 最大連續子陣列
###### tags: `程式設計`
online judge: TCIRC
link: https://judge.tcirc.tw/ShowProblem?problemid=d052
:::info
由於最近參加的線上比賽有遇到類似的概念，因此有感而發，分享這個想法。
:::

## 題目敘述
輸入一個整數陣列 $A[1:n]$，請計算 $A$ 的連續子陣列的最大可能總和，空陣列的和以$0$計算。

## 輸入說明
第一行是正整數 $n$，第二行有 $n$ 整數 $A[1], A[2], \ldots, A[n]$。$n$ 不超過 $1e5$，陣列內容絕對值不超過 $1e9$。

### 範例輸入
$case 1$

8
4 12 -17 5 8 -2 7 -3

$case 2$

3
-1 -1 -1

### 範例輸出
$case 1$

18

$case 2$

0

## 想法
定義 $S_i$ 為第 $i$ 項的前綴和，答案要找的是連續子陣列最大的和，也就是 $S_j - S_i$ 要最大，其中 $i \lt j$，而題目也可以接受空陣列，所以最小的答案會是 $0$。
如此一來，題目就轉化成講義前面的例題 [P-4-12. 一次買賣](https://judge.tcirc.tw/ShowProblem?problemid=d051) ，用前綴和的值去找最大差。

## Code

#include<iostream>
using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	ll mn = 0, mx = 0;
	ll ps = 0, t, ans = 0;
	for (int i = 0;i < n;i++) {
		cin >> t;
		ps += t;
		mn = min(mn, ps);
		ans = max(ans, ps - mn);
	}
	cout << ans << '\n';
	return 0;
}

### Result

- 最後更新 [time=Fri, Sep 24, 2021 10:54 AM]