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

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

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

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

假设：

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

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

代码：

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

    ll maxPrefix = 0;
    ll minPrefix = 0;
    ll curSum = 0;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        curSum += a;
        maxPrefix = max(maxPrefix, curSum);
        minPrefix = min(minPrefix, curSum);
    }

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