[LeetCode] 1749. Maximum Absolute Sum of Any Subarray

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 the maximum 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 <= 105
-104 <= nums[i] <= 104

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-absolute-sum-of-any-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是前缀和，也带一些动态规划的思想。题目要找的是一段子数组，这一段子数组的和要不然非常大要不然非常小，这样才能使得其绝对值是最大的。但是由于子数组的长度是不确定的所以用一般的前缀和的思路应该是会超时的（O(n^2)的复杂度），主要问题是在于我们并不知道子数组的长度。这道题算是个脑筋急转弯吧，思路有点类似前缀和，但是在统计前缀和的时候我们记录一个前缀和里面全局的最大值 max 和全局的最小值 min。那么最大值和最小值的差值这一段组成的子数组的和就一定是满足题意的最大值。又因为题目问的是绝对值所以无所谓 max 先出现还是 min 先出现。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int[] presum = new int[n + 1];
        int max = 0;
        int min = 0;
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + nums[i];
            max = Math.max(max, presum[i + 1]);
            min = Math.min(min, presum[i + 1]);
        }
        return Math.max(0, max - min);
    }
}