1749. Maximum Absolute Sum of Any Subarray

MediumArrayDynamic Programming
Leetcode Link

Problem Description

You are given an array of integers called nums. The task is to find the maximum absolute sum of any subarray of this array. Let's clarify a few things first. A subarray is a contiguous part of the original array, and it can be as small as zero elements or as large as the entire array. The absolute sum is the total sum in which we consider a negative total as its positive counterpart (that is, we apply the absolute value operation to the sum). We can denote it mathematically as abs(sum) where sum is the sum of elements in the subarray. Now, the maximum absolute sum is the highest value of abs(sum) that you can get from all possible subarrays of nums.

Intuition

The intuition behind the solution comes from dynamic programming, a method where we build up to the solution by solving subproblems and using those solutions to solve larger problems. Here, we aim to track two values while iterating through the array: the maximum subarray sum so far and the minimum subarray sum so far. By keeping track of both, we can ensure that we consider both positive and negative numbers effectively because the maximum absolute sum could come from a subarray with a very negative sum due to the absolute value operation.

We define two variables, f and g, that will represent the maximum and minimum subarray sum ending at the current position, respectively. As we move through the array, we keep updating these values. If f drops below zero, we reset it to zero because a subarray with a negative sum would not contribute to a maximum absolute sum; we should instead start a new subarray from the next element. Similarly, if g becomes positive, we reset it to zero, starting a new subarray for the minimum sum calculation.

f keeps track of the maximum sum achieved so far (without taking the absolute value), and g does the same for the minimum sum. Notice that for g, we take the absolute value to compare with the max value f, because we are interested in the maximum absolute sum. Our final answer is the maximum between f and the absolute value of g throughout the entire pass. This is because for a negative subarray to contribute to the maximum absolute sum, its absolute value should be taken which might be larger than the maximum positive subarray sum.

The brilliance of this method lies in the realization that we don't need to maintain a full array of sums, but simply update our two tracking variables as we iterate through nums. This simplifies the process and reduces our space complexity to O(1).

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

How many times is a tree node visited in a depth first search?

Solution Approach

The solution uses a simple yet powerful approach based on dynamic programming, which enables us to keep track of the maximum and minimum sums of subarrays that we have encountered so far. The dynamic programming is apparent in the way we update our running accumulations f and g, and in how they depend solely on the values at the previous index.

Let's go over the logic in detail:

  • We initialize two variables, f and g, to store the current subarray's maximum and minimum sum, respectively.

  • We also have a variable ans to store the global maximum absolute sum that we will eventually return.

  • As we iterate over each element x in nums, we update f and g for every position:

    • f is updated to be the maximum of f reset to 0 (if it was negative) plus the current element x. This effectively means, if accumulating a sum including x leads to a sum less than zero, we are better off starting a new subarray at the next position.

    For f, the state transition can be written as:

    1f[i] = max(f[i - 1], 0) + nums[i]
    • g is updated to be the minimum of g reset to 0 (if it was positive) plus the current element x. This keeps track of the negative sums, which, when their absolute value is taken, may contribute to the absolute sum.

    The state transition for g is:

    1g[i] = min(g[i - 1], 0) + nums[i]

  • After updating f and g with the current element, we update our answer ans to be the maximum of ans, f, and the absolute value of g. This ensures that ans always holds the highest value of either the current maximum subarray sum, or the absolute value of the current minimum subarray sum.

  • After the loop completes, ans holds the maximum absolute sum possible from all the subarrays of nums.

The beauty of this algorithm lies in the fact that it computes the answer in a single pass through the input array with O(n) time complexity, where n is the length of nums, and it does so with O(1) additional space complexity, since it doesn't require storing an array of sums.

Remember, the original problem allowed for the subarray to be empty, which would mean an absolute sum of 0. However, this scenario is naturally covered in our implementation because the initialization of ans starts at 0, and f and g can only increase from there.

The solution could also be seen as an adaptation of the famous Kadane's algorithm, which is used to find the maximum sum subarray, here cleverly tweaked to also account for negative sums by the introduction of g and maximizing the absolute values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's consider an example nums array to illustrate the solution approach:

1nums = [2, -1, -2, 3, -4]

We want to find the maximum absolute sum of any subarray of this array.

  • Initialize f and g to 0. f is the maximum subarray sum so far, and g is the minimum subarray sum so far. Also, initialize ans to 0, which will hold the final answer.
  • Start iterating over the nums array.

  1. First element is 2:

    • Update f: f = max(0, 0) + 2 = 2
    • Update g: g = min(0, 0) + 2 = 2
    • Update ans: ans = max(0, 2, abs(2)) = 2

  2. Second element is -1:

    • Update f: f = max(2, 0) - 1 = 1
    • Update g: g = min(2, 0) - 1 = -1
    • Update ans: ans = max(2, 1, abs(-1)) = 2

  3. Third element is -2:

    • Update f: f = max(1, 0) - 2 = -1 (But since f is now less than 0, we reset it to 0)
    • Update g: g = min(-1, 0) - 2 = -3
    • Update ans: ans = max(2, 0, abs(-3)) = 3

  4. Fourth element is 3:

    • Update f: f = max(0, 0) + 3 = 3
    • Update g: g = min(-3, 0) + 3 = 0 (But since g would become positive, we reset it to 0)
    • Update ans: ans = max(3, 3, abs(0)) = 3

  5. Fifth element is -4:

    • Update f: f = max(3, 0) - 4 = -1 (Again, reset f to 0 since it's less than 0)
    • Update g: g = min(0, 0) - 4 = -4
    • Update ans: ans = max(3, 0, abs(-4)) = 4
  • After iterating through the entire array, the final answer (ans) is 4, which is the maximum absolute sum of any subarray in nums.

Thus, in this example, the maximum absolute sum is 4, obtained from the subarray [-4] whose absolute sum is abs(-4) = 4.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxAbsoluteSum(self, nums: List[int]) -> int:
5        """
6        This function finds the maximum absolute sum of any non-empty subarray of the given array.
7      
8        Args:
9        nums: List[int] - the list of integers over which we want to find the maximum absolute sum.
10      
11        Returns:
12        The maximum absolute subarray sum.
13        """
14      
15        # f_max keeps track of the maximum subarray sum ending at the current position.
16        # g_min keeps track of the minimum subarray sum ending at the current position.
17        f_max = g_min = 0
18      
19        # ans stores the maximum absolute sum found so far.
20        ans = 0
21      
22        # Iterate through each number in nums.
23        for num in nums:
24            # Update the maximum subarray sum ending at the current position. 
25            # Reset to current number if the max sum becomes negative.
26            f_max = max(f_max, 0) + num
27          
28            # Update the minimum subarray sum ending at the current position. 
29            # Reset to current number if the min sum becomes positive.
30            g_min = min(g_min, 0) + num
31          
32            # Update the ans with the larger value between the current ans,
33            # the current maximum subarray sum, and the absolute value of
34            # the current minimum subarray sum.
35            ans = max(ans, f_max, abs(g_min))
36      
37        # Return the maximum absolute subarray sum found.
38        return ans
39
1class Solution {
2    public int maxAbsoluteSum(int[] nums) {
3        int maxEndingHere = 0; // Represents the maximum subarray sum ending at the current position
4        int minEndingHere = 0; // Represents the minimum subarray sum ending at the current position
5        int maxAbsoluteSum = 0; // Keeps track of the maximum absolute subarray sum
6
7        // Traverse the array
8        for (int num : nums) {
9            // Calculate the maximum subarray sum ending here by taking the maximum of
10            // the current maximum subarray sum (extended by the current number) and 0
11            maxEndingHere = Math.max(maxEndingHere + num, 0);
12
13            // Calculate the minimum subarray sum ending here by taking the minimum of
14            // the current minimum subarray sum (extended by the current number) and 0
15            minEndingHere = Math.min(minEndingHere + num, 0);
16
17            // Calculate the current maximum absolute subarray sum by taking the maximum of
18            // the current maximum absolute sum, the current maximum subarray sum ending here,
19            // and the absolute value of the current minimum subarray sum ending here
20            maxAbsoluteSum = Math.max(maxAbsoluteSum, Math.max(maxEndingHere, Math.abs(minEndingHere)));
21        }
22
23        // Return the overall maximum absolute subarray sum found
24        return maxAbsoluteSum;
25    }
26}
27
1class Solution {
2public:
3    // Function to calculate the maximum absolute sum of any subarray of nums
4    int maxAbsoluteSum(vector<int>& nums) {
5        // Initialize the variables to keep track of the current max and min subarray sum
6        int currentMaxSum = 0;
7        int currentMinSum = 0;
8      
9        // Variable to store the final maximum absolute sum
10        int maxAbsoluteSum = 0;  
11
12        // Iterate over the numbers in the vector
13        for (int& num : nums) {
14          
15            // Update currentMaxSum: reset to zero if it becomes negative, then add the current element
16            currentMaxSum = max(0, currentMaxSum) + num;
17          
18            // Update currentMinSum: reset to zero if it is positive, then add the current element
19            currentMinSum = min(0, currentMinSum) + num;
20          
21            // Find the maximum between currentMaxSum and the absolute value of currentMinSum
22            // Update maxAbsoluteSum if necessary
23            maxAbsoluteSum = max({maxAbsoluteSum, currentMaxSum, abs(currentMinSum)});
24        }
25      
26        // Return the final maximum absolute sum
27        return maxAbsoluteSum;
28    }
29};
30
1function maxAbsoluteSum(nums: number[]): number {
2    // Initialize local variables to track the maximum subarray sum and the minimum subarray sum
3    let maxSubarraySum = 0; // f represents the maximum potential subarray sum at the current index
4    let minSubarraySum = 0; // g represents the minimum potential subarray sum at the current index
5    let maxAbsoluteSumResult = 0; // ans is the final answer tracking the maximum absolute sum found
6
7    // Iterate through the array of numbers
8    for (const num of nums) {
9        // Update the maximum subarray sum: reset to 0 if negative, or add current number
10        maxSubarraySum = Math.max(maxSubarraySum, 0) + num;
11
12        // Update the minimum subarray sum: reset to 0 if positive, or add current number
13        minSubarraySum = Math.min(minSubarraySum, 0) + num;
14
15        // Update the maximum absolute sum found so far by comparing it with the
16        // current maximum subarray sum and the absolute value of the current minimum subarray sum
17        maxAbsoluteSumResult = Math.max(maxAbsoluteSumResult, maxSubarraySum, -minSubarraySum);
18    }
19
20    // Return the maximum absolute sum of any subarray
21    return maxAbsoluteSumResult;
22}
23
Not Sure What to Study? Take the 2-min Quiz

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time complexity

The time complexity of the provided code is O(n) since it passes through the array nums once, performing a constant amount of work for each element in the array. No nested loops or recursive calls are present that would increase the complexity. Here n is the length of the array nums.

Space complexity

The space complexity of the code is O(1) because the space used does not grow with the size of the input array. Only a fixed number of variables f, g, and ans are used, irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«