题解 | #子数组绝对值的最大值#

子数组的和可以表示为两个前缀和的差值。 设 为数组 的前缀和，即 ，并定义 。 那么，从索引 到 的子数组和 可以表示为：

我们要找的最大值是 。 根据绝对值的性质， 实际上是所有前缀和（包括 到 ）中任意两个值之间的最大差值。

要最大化 ，我们只需要找到所有前缀和中的最大值和最小值，然后计算它们之间的差值。

假设：

• 所有前缀和中的最大值是
• 所有前缀和中的最小值是

那么，子数组和的绝对值的最大值就是：

代码：

#include <bits/stdc++.h>
#include <limits>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ll> prefix(n);
    ll maxPrefix = 0;
    ll minPrefix = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        prefix[i] = (i > 0 ? prefix[i - 1] : 0) + a;
        maxPrefix = max(maxPrefix, prefix[i]);
        minPrefix = min(minPrefix, prefix[i]);
    }

    cout << (maxPrefix - minPrefix) << endl;
}