Medium

题目描述

给你一个整数数组 nums。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的绝对和是 abs(numsl + numsl+1 + ... + numsr-1 + numsr)。

返回 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^5
  • -10^4 <= nums[i] <= 10^4

解题思路

这道题的关键洞察是：子数组的最大绝对和要么是最大子数组和，要么是最小子数组和的绝对值。

思路分析：

  1. 转换问题：绝对值的最大值只能来自两种情况：

    • 正数的最大值（即最大子数组和）
    • 负数的绝对值最大值（即最小子数组和的相反数）

  2. 使用Kadane算法：我们需要分别计算：

    • 最大子数组和（标准Kadane算法）
    • 最小子数组和（Kadane算法的变形）

  3. 具体实现：

    • 用两个变量分别维护当前最大/最小子数组和
    • 用两个变量分别记录全局最大/最小子数组和
    • 最终答案是 max(最大子数组和, |最小子数组和|)

这种方法的优势是只需要遍历一次数组，时间复杂度为O(n)，空间复杂度为O(1)。

推荐解法：一次遍历同时计算最大和最小子数组和，然后取两者绝对值的最大值。

代码实现

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int maxSum = 0, minSum = 0;
        int curMax = 0, curMin = 0;
        
        for (int num : nums) {
            curMax = max(num, curMax + num);
            curMin = min(num, curMin + num);
            maxSum = max(maxSum, curMax);
            minSum = min(minSum, curMin);
        }
        
        return max(maxSum, -minSum);
    }
};

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_sum = min_sum = 0
        cur_max = cur_min = 0
        
        for num in nums:
            cur_max = max(num, cur_max + num)
            cur_min = min(num, cur_min + num)
            max_sum = max(max_sum, cur_max)
            min_sum = min(min_sum, cur_min)
        
        return max(max_sum, -min_sum)

public class Solution {
    public int MaxAbsoluteSum(int[] nums) {
        int maxSum = 0, minSum = 0;
        int curMax = 0, curMin = 0;
        
        foreach (int num in nums) {
            curMax = Math.Max(num, curMax + num);
            curMin = Math.Min(num, curMin + num);
            maxSum = Math.Max(maxSum, curMax);
            minSum = Math.Min(minSum, curMin);
        }
        
        return Math.Max(maxSum, -minSum);
    }
}

var maxAbsoluteSum = function(nums) {
    let maxSum = 0, minSum = 0;
    let curMax = 0, curMin = 0;
    
    for (let num of nums) {
        curMax = Math.max(num, curMax + num);
        curMin = Math.min(num, curMin + num);
        maxSum = Math.max(maxSum, curMax);
        minSum = Math.min(minSum, curMin);
    }
    
    return Math.max(maxSum, -minSum);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需遍历数组一次
空间复杂度O(1)只使用常数个额外变量

相关题目