1749. Maximum Absolute Sum of Any Subarray

Problem

You are given an integer array nums. The absolute sum of a subarray [numsₗ, numsₗ₊₁, ..., numsᵣ₋₁, numsᵣ] is abs(numsₗ + numsₗ₊₁ + ... + numsᵣ₋₁ + numsᵣ).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

Constraints:

• 1 <= nums.length <= 10⁵
• -104 <= nums[i] <= 10⁴

Test Cases

1
2

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('nums, expected', [
    ([1,-3,2,3,-4], 5),
    ([2,-5,1,-4,3,-2], 8),

    ([-3,-5,-3,-2,-6,3,10,-10,-8,-3,0,10,3,-5,8,7,-9,-9,5,-8], 27),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, nums, expected):
    assert sol.maxAbsoluteSum(nums) == expected

Thoughts

可以直接搬 53. Maximum Subarray 的代码，在求子数组最大和 largest 的同时，用完全类似的方法求出子数组的最小和 smallest。最终结果即为 max{largest, smallest}。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        sl = largest = nums[0]
        ss = smallest = nums[0]
        for i in range(1, len(nums)):
            sl = max2(sl, 0) + nums[i]
            largest = max2(largest, sl)

            ss = min2(ss, 0) + nums[i]
            smallest = min2(smallest, ss)

        return max2(largest, -smallest)

Another Way

从 nums 最左端开始，计算出前 0 个数字（即空数组）之和、前 1 个数字之和、前 2 个数字之和、……、前 n - 1 个数字之和、以及所有（n 个）数字之和。取这 n + 1 个前缀和中的最大值 mx 与最小值 mn，那么 mx - mn 即为绝对值最大的子数组之和。

时间复杂度 O(n)，空间复杂度 O(n)（也可以直接边累加边求 mx 和 mn，那么空间复杂度也是 O(1)）。

1
2
3
4
5
6
7

from itertools import accumulate


class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        sums = list(accumulate(nums, initial=0))
        return max(sums) - min(sums)

参考资料

• 本文引用

  • 53. Maximum Subarray

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章