题解 | #最大子串和#

一、暴力O(n^2)

二、分治O(nlogn)

从中间分开，分别比较分割线左、分割线右、包含分割线的三个区间。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1000010];
int maxx(int l, int r) {
    int mid = (l + r) / 2;
    if(l == r) return a[l];
    int ans = max(maxx(l, mid), maxx(mid + 1, r));
    int ll = 0, rr = 0, tmp = 0;
    for(int i = mid + 1; i <= r; i ++) {
        tmp += a[i];
        ll = max(ll, tmp);
    }
    tmp = 0;
    for(int i = mid; i >= l; i --) {
        tmp += a[i];
        rr = max(rr, tmp);
    }
    ans = max(ans, ll + rr);
    return ans;
}
signed main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    int num = maxx(1, n);
    cout << num << endl;
    return 0;
}

三、贪心O(n)

先求前缀和，答案在s[j] - s[i - 1]的遍历中出现
固定s[j]后找s[i - 1]的最小值。可以提前处理前缀和最小值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1000010], maxx[1000010], s[1000010];
signed main() {
    scanf("%lld", &n);
    memset(maxx, 0, sizeof maxx);
    for(int i = 1; i <= n; i ++) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i ++) {
        maxx[i] = min(maxx[i - 1], s[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        ans = max(ans, s[i] - maxx[i]);
    }
    cout << ans << endl;
    return 0;
}

四、动态规划O(n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, ans, a[1000010], f[1000010];
signed main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i ++) {
        f[i] = max(a[i], f[i - 1] + a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
}