## HƯỚNG DẪN
pre[i]: tổng lớn nhất của 1 subarray trong đoạn [1, n].\
mid[i]: tổng lớn nhất của 2 subarray không giao nhau trong đoạn [1, n].\
suf[i]: tổng lớn nhất của 1 subarray trong đoạn [i, n].\
sumf[i]: tổng đoạn [1, n].\
**Đáp án:** max(mid[i], suf[i+1]), 1 ≤ i ≤ n - 1
Mảng pre và suf được tính như bài [Mảng con có tổng lớn nhất 2](https://marisaoj.com/problem/508).
mid[i] = max(mid[i-1], sumf[i] + max(pre[j] - sumf[j])), 1 ≤ j ≤ i ≤ n.
Code:
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORD(i,a,b) for(int i=a; i>=b; --i)
template<class X, class Y>
bool maximize(X &x, const Y &y){return (x < y) ? x = y, 1 : 0;}
const int MAXN = 1e5 + 5;
const ll INF = 9e18;
int n;
ll a[MAXN];
ll pre[MAXN], mid[MAXN], suf[MAXN], sumf[MAXN];
ll sum, cur = -INF, res = -INF;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
FOR(i,1,n) cin >> a[i];
FOR(i,0,n+1)
{
pre[i] = mid[i] = suf[i] = -INF;
if (1 <= i && i <= n) sumf[i] = sumf[i-1] + a[i];
}
sum = 0;
FOR(i,1,n)
{
sum += a[i];
maximize(pre[i], pre[i-1]);
maximize(pre[i], sum);
maximize(sum, 0);
maximize(cur, pre[i] - sumf[i]);
maximize(mid[i], mid[i-1]);
maximize(mid[i], sumf[i] + cur);
}
sum = 0;
FORD(i,n,1)
{
sum += a[i];
maximize(suf[i], suf[i+1]);
maximize(suf[i], sum);
maximize(sum, 0);
maximize(res, mid[i] + suf[i+1]);
}
return cout << res,0;
}
```
hungkm466
Created at
3 likes