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

这是一份基于你提供的代码生成的详细题解文档。

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

🎯 问题描述

描述：
给你一个整数数组 nums。
子数组 nums[l...r] 的和定义为 $nums[l] + nums[l+1] + ... + nums[r]$。
你需要找出所有可能的子数组和中，绝对值最大的那一个。
即求 $\max(|Sum(l, r)|)$，其中 $0 \le l \le r < n$。

说明：

• 这是一个前缀和结合数学推导的问题。

• 核心策略：

  • 任意子数组的和都可以表示为两个前缀和之差：$Sum(l, r) = pre[r+1] - pre[l]$。
  • 我们要最大化 $|pre[r+1] - pre[l]|$。
  • 这等价于在 pre 数组中找到两个数，使它们的差值的绝对值最大。
  • 显然，这个最大值等于 pre 数组中的最大值减去最小值。

• 示例：

• 示例 1：

输入：nums = [1,-3,2,3,-4]
输出：5
解释：
- 前缀和 pre = [0, 1, -2, 0, 3, -1]
- 子数组 [2,3] (即 nums[2]+nums[3] = 2+3=5) 的绝对值为 5。
- 子数组 [1,-3,2,3] (即 nums[0]...nums[3] = 3) 的绝对值为 3。
- 最大绝对值为 5。
- 根据算法：max(pre) = 3, min(pre) = -2。结果 = 3 - (-2) = 5。

💻 解题思路

思路1：前缀和极值差

核心逻辑

1. 构建前缀和数组 pre：
   • pre[0] = 0（表示空前缀的和）。
   • pre[i+1] = pre[i] + nums[i]。
   • pre[i] 表示 nums[0] 到 nums[i-1] 的和。
2. 数学转化：
   • 任意子数组 nums[l...r] 的和可以表示为 $S = pre[r+1] - pre[l]$。
   • 我们需要求 $\max(|S|) = \max(|pre[r+1] - pre[l]|)$。
   • 绝对值 $|A - B|$ 的最大值，一定等于数组中的最大值减去最小值。
   • 即 $\max(pre) - \min(pre)$。
3. 计算结果：
   • 直接返回 max(pre) - min(pre)。

代码实现

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 1. 构建前缀和数组
        # pre[0] = 0 表示空子数组的和
        pre = [0] * (n + 1)
        
        for i, num in enumerate(nums):
            pre[i+1] = pre[i] + num
            
        # 2. 返回前缀和数组的最大值与最小值的差
        # 原理：任意子数组和 = pre[j] - pre[i]
        # 要使 |pre[j] - pre[i]| 最大，即取最大值减最小值
        return max(pre) - min(pre)

📊 性能分析

• 时间复杂度：$O(N)$
  • 构建前缀和数组：$O(N)$。
  • 查找最大值和最小值：$O(N)$。
  • 总体线性时间。
• 空间复杂度：$O(N)$
  • 需要一个长度为 $N+1$ 的 pre 数组。
  • 注：其实可以优化到 $O(1)$ 空间，只需在遍历过程中维护当前的 min_pre 和 max_pre 即可，不需要存储整个数组。

思考

1. 为什么 pre 数组要包含 0？

   • pre[0] = 0 代表空前缀。
   • 如果不包含 0，我们就无法表示从下标 0 开始的子数组（即 l=0 的情况）。
   • 例如，如果整个数组的和最大，那么 $Sum(0, n-1) = pre[n] - pre[0]$。

2. 数学证明：

   • 我们要最大化 $|x - y|$，其中 $x, y \in pre$。
   • 情况1：$x \ge y$，则 $|x - y| = x - y$。要最大化它，需 $x$ 最大，$y$ 最小。
   • 情况2：$x < y$，则 $|x - y| = y - x$。要最大化它，需 $y$ 最大，$x$ 最小。
   • 综上，最大值总是 $\max(pre) - \min(pre)$。

3. 空间优化版本：

   • 由于我们只需要最大值和最小值，不需要回溯具体的子数组，因此不需要存储整个 pre 数组。
   • 可以在一次遍历中完成：

     # 空间优化版本
     current_sum = 0
     min_pre = 0
     max_pre = 0
     
     for num in nums:
         current_sum += num
         min_pre = min(min_pre, current_sum)
         max_pre = max(max_pre, current_sum)
         
     return max_pre - min_pre

4. 与最大子数组和的区别：

   • 最大子数组和（Kadane算法）只关心正数累积。
   • 本题关心绝对值，所以既要看最大的正累积，也要看最小的负累积（因为 $|负数|$ 可能很大）。