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

发表于 分类于 阅读次数： Waline： 本文字数： 721 阅读时长 ≈ 2 分钟

考点

  • 最大子数组和

思路

一、问题描述

给定一个长度为 \(n\) 的整数数组 \[ \texttt{nums} = [a_1, a_2, \dots, a_n] \] 要求在所有非空连续子数组中，找到其元素和的绝对值最大值，即： \[ \max_{1 \le l \le r \le n} \left| \sum_{i=l}^{r} a_i \right| \]

二、问题建模

1. 等价拆分

绝对值最大值可以拆成两个独立问题： \[ \max \left( \max_{l,r} \sum_{i=l}^{r} a_i, \; -\min_{l,r} \sum_{i=l}^{r} a_i \right) \] 也就是说：

  • 最大子数组和
  • 最小子数组和（绝对值取反）

只要同时求出这两者，答案即可直接得到。

2. 子数组和的经典模型

这是一个典型的 最大子数组和（Kadane）模型：

  • 设 \[ dp^{\max}_i = \text{以 } i \text{ 结尾的最大子数组和} \]

  • 状态转移： \[ dp^{\max}_i = \max(a_i, dp^{\max}_{i-1} + a_i) \]

同理，最小子数组和：

  • 设 \[ dp^{\min}_i = \text{以 } i \text{ 结尾的最小子数组和} \]

  • 状态转移： \[ dp^{\min}_i = \min(a_i, dp^{\min}_{i-1} + a_i) \]

三、算法思路

1. 动态规划压缩

不需要维护完整的 DP 数组，只需记录：

  • pre_mx：当前以位置 \(i\) 结尾的最大子数组和
  • pre_mi：当前以位置 \(i\) 结尾的最小子数组和

以及全局最优值：

  • mx：所有位置中出现过的最大子数组和
  • mi：所有位置中出现过的最小子数组和

2. 初始化

  • 初始时，子数组至少包含一个元素：

    1
    2
    pre_mx = nums[0];
    pre_mi = nums[0];

  • 全局答案允许“什么都不选”（即 0），因此：

    1
    2
    mx = max(0, pre_mx);
    mi = min(0, pre_mi);

3. 状态转移（单次遍历）

对每个元素 nums[i]：

  • 更新最大子数组和： \[ pre\_mx = \max(nums[i], pre\_mx + nums[i]) \]

  • 更新最小子数组和： \[ pre\_mi = \min(nums[i], pre\_mi + nums[i]) \]

  • 同步维护全局最优值： \[ mx = \max(mx, pre\_mx) \]

    \[ mi = \min(mi, pre\_mi) \]

4. 最终答案

\[ \text{answer} = \max(mx, -mi) \]

四、正确性说明（简要）

  • 任意连续子数组要么产生最大的正和，要么产生最小的负和
  • Kadane 算法保证枚举了所有以每个位置结尾的最优子数组
  • 同时维护最大与最小，即完整覆盖绝对值两侧
  • 因此算法正确

五、复杂度分析

  • 时间复杂度： \[ O(n) \]

  • 空间复杂度： \[ O(1) \]

六、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        // pre_mx: 以当前位置结尾的最大子数组和
        // pre_mi: 以当前位置结尾的最小子数组和
        int pre_mx = nums[0], pre_mi = nums[0];

        // mx: 全局最大子数组和
        // mi: 全局最小子数组和
        int mx = max(0, pre_mx);
        int mi = min(0, pre_mi);

        for (int i = 1; i < nums.size(); ++i) {
            // Kadane：最大子数组
            pre_mx = max(nums[i], pre_mx + nums[i]);
            mx = max(mx, pre_mx);

            // Kadane：最小子数组
            pre_mi = min(nums[i], pre_mi + nums[i]);
            mi = min(mi, pre_mi);
        }

        // 绝对值最大值来自正向最大或负向最小
        return max(mx, -mi);
    }
};