Select solution language
Write solution here.
## Hướng dẫn
Cố định i. \
Gọi:
- pre[i] là tổng lớn nhất trong đoạn [1, i]
- suf[i] là tổng lớn nhất trong đoạn [i, n]
**Đáp án bài toán là: max(pre[i-1] + suf[i], pre[i] + suf[i+1]), 2 ≤ i ≤ n - 1**
**Code: O(n)**
```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
int n;
ll a[MAXN], pre[MAXN], suf[MAXN];
ll sum;
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORD(i,a,b) for(int i=a; i>=b; --i)
bool maximize(ll &a, const ll &b)
{
return (a < b) ? a = b, 1 : 0;
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
FOR(i,0,n+1) pre[i] = suf[i] = LLONG_MIN;
sum = 0;
FOR(i,1,n)
{
cin >> a[i];
sum += a[i];
maximize(pre[i], pre[i-1]);
maximize(pre[i], sum);
maximize(sum, 0);
}
sum = 0;
ll ans = LLONG_MIN;
FORD(i,n,1)
{
sum += a[i];
maximize(suf[i], suf[i+1]);
maximize(suf[i], sum);
maximize(sum, 0);
if (i-1 >= 1) maximize(ans, pre[i-1] + suf[i]);
if (i+1 <= n) maximize(ans, pre[i] + suf[i+1]);
}
cout << ans;
return 0;
}
```
hungkm466
Created at
0 likes