What is the maximum absolute sum of any subarray problem about?

The problem asks for the maximum absolute sum of any subarray in a given integer array, using dynamic programming to compute this in linear time.

How does dynamic programming apply to the maximum absolute sum problem?

Dynamic programming tracks the running sums of subarrays and uses state transitions to efficiently compute the maximum absolute sum, optimizing both time and space.

What are the key challenges when solving this problem?

The challenges lie in handling negative sums and ensuring that the solution works within O(N) time and O(1) space constraints.

What is the space complexity of the maximum absolute sum problem?

The space complexity is O(1), as the solution only requires a few variables to store the current sums and maximum absolute sum.

How does the problem change if we ask for the maximum sum instead of the absolute sum?

If we ask for the maximum sum, the absolute value operation would not be necessary, and the problem would focus on finding the subarray with the largest sum directly.

#1749

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 nums 。一个子数组 [nums l , nums l+1 , ..., nums r-1 , nums r ] 的和的绝对值为 abs(nums l + nums l+1 + ... + nums r-1 + nums r ) 。请你找出 nums 中和的绝对值最大的…

数组动态规划

题目描述

给你一个整数数组 nums 。一个子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] 的 和的绝对值 为 abs(nums_l + nums_l+1 + ... + nums_r-1 + nums_r) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

abs(x) 定义如下：

如果 x 是负整数，那么 abs(x) = -x 。
如果 x 是非负整数，那么 abs(x) = x 。

示例 1：

输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。

示例 2：

输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。

提示：

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以 $nums[i]$ 结尾的子数组的和的最大值，定义 $g[i]$ 表示以 $nums[i]$ 结尾的子数组的和的最小值。那么 $f[i]$ 和 $g[i]$ 的状态转移方程如下：

\begin{aligned} f[i] &= \max(f[i - 1], 0) + nums[i] \\ g[i] &= \min(g[i - 1], 0) + nums[i] \end{aligned}

最后答案为 $max(f[i], |g[i]|)$ 的最大值。

由于 $f[i]$ 和 $g[i]$ 只与 $f[i - 1]$ 和 $g[i - 1]$ 有关，因此我们可以使用两个变量代替数组，将空间复杂度降低到 $O(1)$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently optimize space usage with dynamic programming?
question_mark
How well does the candidate handle state transitions in dynamic programming problems?
question_mark
Does the candidate understand how to compute absolute sums within subarrays efficiently?

warning

常见陷阱

外企场景

error
Forgetting to consider the possibility of empty subarrays, which can affect the result when calculating the maximum absolute sum.
error
Not handling negative numbers correctly in the subarray sums and absolute value calculations.
error
Overcomplicating the problem by using unnecessary data structures, when a solution with constant space can be achieved.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we asked for the maximum sum, rather than the absolute sum? This would eliminate the need to consider the negative sum possibilities.
arrow_right_alt
How would the solution change if the array contained only positive numbers or only negative numbers?
arrow_right_alt
What if we asked for the subarray with the smallest absolute sum instead?

help

常见问题

外企场景

继续练习

#1751 最多可以参加的会议数目 II #1755 最接近目标值的子序列和 #1735 生成乘积数组的方案数