This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1749 on LeetCode. The maximum absolute value of the sum of any subarray, with medium difficulty.

Tag: prefix and

Give you an integer array nums.

A subarray [numsl, numsl+1,…, numsr-1, numsr] has the “absolute value of sum” as abs(numsl + numsl+1 +… + numsr-1 + NUMsr).

Find any subarray of nums with the largest (possibly empty) absolute value of and and return that maximum.

Abs (x) is defined as follows:

  • If x is a negative integer, then abs of x is equal to minus x.

  • If x is a non-negative integer, then abs of x is equal to x.

Example 1:

Nums = [1, 3,2,3,-4]; nums = [1, 3,2,3,-4];Copy the code

Example 2:

Input: nums = [2, 5, 1, 4, 3, 2] output: 8: subarray [- 5, 1, 4] and the absolute value of the largest, for abs (5 + 1-4) = abs (8) = 8.Copy the code

Tip:

  • 1 <= nums.length <=
    1 0 5 10^5
  • –
    1 0 4 10^4     <= nums[i] <=
    1 0 4 10^4

The prefix and

They want us to take the sum of the subarrays of contiguous segments, so it’s natural to think of the sum of prefixes.

Sum [j] -sum [i-1] : sum[j] -sum [i-1] : sum[j] -sum [i-1] : sum[j] -sum [i-1] : sum[j] -sum [i-1]

Abs (sum[j] -sum [I – 1]) = abs(sum[j] -sum [I – 1])

  • Find the maximum in the prefix and array minus the minimum to get a maximum positive number (provided the maximum comes after the minimum and the minimum is a negative number, otherwise the maximum should be taken directly)
  • Find the minimum of the prefix sum minus the maximum to get a minimum negative number (provided the minimum comes after the maximum and the maximum is a positive number, otherwise take the minimum directly as the answer).

That is, the final answer depends only on the maximum and minimum values in the prefix and array, and the maximum may appear before or after the minimum.

So we can update the answers as we go through the loop.

Code:

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        int ans = 0;
        for (int i = 1, min = 0, max = 0; i <= n; i++) {
            ans = Math.max(ans, Math.abs(sum[i] - min));
            ans = Math.max(ans, Math.abs(sum[i] - max));
            max = Math.max(max, sum[i]);
            min = Math.min(min, sum[i]);
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.1749 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.