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

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return _themaximum 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.

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

题目大意

给你一个整数数组 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

解题思路

题目要求找到数组的最大绝对子数组和，即：max(|最大子数组和|, |最小子数组和|)。

可以利用 Kadane's Algorithm 分别求解 最大子数组和 和 最小子数组和，然后取绝对值的最大值。

1. 定义变量：

   • maxEndingHere 记录以当前值结尾的最大子数组和
   • maxSoFar 记录 最大子数组和
   • minEndingHere 记录以当前值结尾的最小子数组和
   • minSoFar 记录 最小子数组和

2. 遍历 nums：

   • maxEndingHere = max(nums[i], maxEndingHere + nums[i])
     • 选择 nums[i] 或继续扩展当前最大子数组
   • maxSoFar = max(maxSoFar, maxEndingHere)
     • 更新最大子数组和
   • minEndingHere = min(nums[i], minEndingHere + nums[i])
     • 选择 nums[i] 或继续扩展当前最小子数组
   • minSoFar = min(minSoFar, minEndingHere)
     • 更新最小子数组和

3. 返回：

   • Math.max(Math.abs(maxSoFar), Math.abs(minSoFar))

复杂度分析

• 时间复杂度：O(n)，只遍历数组一次。
• 空间复杂度：O(1)，只使用了常数变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAbsoluteSum = function (nums) {
	let maxEndingHere = 0;
	let maxSoFar = 0;
	let minEndingHere = 0;
	let minSoFar = 0;

	for (let num of nums) {
		maxEndingHere = Math.max(num, maxEndingHere + num);
		maxSoFar = Math.max(maxSoFar, maxEndingHere);
		minEndingHere = Math.min(num, minEndingHere + num);
		minSoFar = Math.min(minSoFar, minEndingHere);
	}

	return Math.max(Math.abs(maxSoFar), Math.abs(minSoFar));
};

相关题目

题号	标题	题解	标签	难度	力扣
53	最大子数组和	[✓]	数组 分治 动态规划	🟠	🀄️ 🔗