Solutions of Maximum sum subarray 2

Select solution language

hungkm466 Created at 13 likes

## 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; }$