任意子数组和的绝对值的最大值 图解题解

1749 要的『绝对值最大』和求最大和差在哪

给一个整数数组 nums。子数组是数组里挨着的一小段（必须连续、不能跳着挑），把它加起来再取绝对值（负变正、正不变），题目要找绝对值最大的那一段。子数组允许取空、空和为 0，答案至少是 0。题面的 [2,-5,1,-4,3,-2] 答案是 8，来自 [-5,1,-4]，和 -8 取绝对值正好 8。

n²/2 条子数组全枚举，为什么大数组吃不消

长度 n 的数组里挨着的子数组约有 n²/2 条，全枚举、逐段取绝对值比大小就是 O(n²)（大 O 记号描述数据规模变大时操作数怎么涨）；每段再从头加一遍求和会退化到 O(n³)。数据一大就跑不动，且相邻子数组的和大量重叠、白白重算。

绝对值最大，该往正的追还是往负的追

绝对值最大有两种来路：这段和要么正得最多，要么负得最多、取绝对值后反而大。只找最大和会漏掉很负的段，反过来又漏掉纯正的段，所以最大和、最小和各算一遍，答案取绝对值更大的那个。

还有个等价看法：任何一段的和 = 两个前缀和相减（前缀和就是从开头一直加到某个位置的累计和）。把见过的前缀和最大值记 maxP、最小值记 minP，答案就是 maxP 减 minP。maxP、minP 谁前谁后无所谓：minP 在后时这段和是负的，取绝对值恰好还是 maxP 减 minP。「一个数都不加」的空前缀 P0 = 0 也要算进候选。

参考代码为什么用 f、g 两个变量、不画前缀和

参考代码不存整条前缀和，而是用两个滚动变量（只留最近状态、循环覆盖旧值）边扫边追。f 记「以当前元素结尾的最大子数组和」，每步 f = max(f, 0) + x：前面攒的是负担（负数）就丢掉、从当前元素重开，否则接着加；g 记「以当前元素结尾的最小子数组和」，对称写成 g = min(g, 0) + x。这套扫法就是 Kadane（求最大子数组和的经典一遍扫描）。

每一步 ans = max(ans, f, |g|)：f 取原值、g 取绝对值，和 maxP 减 minP 算的是同一个答案。

拿 [2,-5,1,-4,3,-2] 亲手滚一遍前缀和

从空前缀 P0 = 0 起步一格格累加：P1 = 0+2 = 2；P2 = 2+(-5) = -3；P3 = -3+1 = -2；P4 = -2+(-4) = -6；P5 = -6+3 = -3；P6 = -3+(-2) = -5。一路只盯两个数：maxP 停在 2（在 P1），minP 降到 -6（在 P4）。

答案 = maxP 减 minP = 2 减 -6 = 8。这个差对应 P1 和 P4 之间的子数组 [-5,1,-4]，和 -8 取绝对值就是 8。

漏掉空前缀 P0 = 0，单个负数为什么会算错

全程只扫一遍，时间 O(n)（n 是数组长度）；只用 maxP、minP（或 f、g）和 ans 几个变量，空间 O(1)。

漏掉空前缀 P0 = 0 是最常见的坑：只有一个负数 [-7] 时，全靠空前缀 0 兜底让答案取到 |-7| = 7，少了这一票就答成 -7。另一处是只追一个方向：答案来自最负那段时，光找最大和就把它漏掉了——此时 maxP 恰好是空前缀 0，同样得靠它才减得出。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        f = g = 0
        ans = 0
        for x in nums:
            f = max(f, 0) + x
            g = min(g, 0) + x
            ans = max(ans, f, abs(g))
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int f = 0, g = 0;
        int ans = 0;
        for (int& x : nums) {
            f = max(f, 0) + x;
            g = min(g, 0) + x;
            ans = max({ans, f, abs(g)});
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int f = 0, g = 0;
        int ans = 0;
        for (int x : nums) {
            f = Math.max(f, 0) + x;
            g = Math.min(g, 0) + x;
            ans = Math.max(ans, Math.max(f, Math.abs(g)));
        }
        return ans;
    }
}