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:
x is a negative integer, then abs(x) = -x.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] <= 104This approach involves modifying Kadane's algorithm to calculate not only the maximum subarray sum but also the minimum subarray sum. The idea is to maintain two running sums: one for the maximum subarray sum and one for the minimum subarray sum.
The maximum absolute sum will be the maximum of the absolute values of these two sums. While iterating through the array, update the maximum and minimum subarray sums by including the current element or starting anew from the current element.
This solution calculates both the maximum and minimum subarray sums while iterating through the array once. It keeps track of the maximum absolute value between the current maximum and minimum subarray sums in each iteration.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array, because we only make a single pass through the array.
Space Complexity: O(1), as we use a constant amount of extra space.
This approach involves calculating the prefix sum of the array while simultaneously tracking the minimum and maximum prefix sums encountered. The maximum absolute sum of a subarray is then given by the largest absolute difference between any two prefix sums, effectively handled by keeping track of the minimum and maximum values of the running prefix sums. This approach leverages the fact that a subarray sum can be expressed as the difference between two prefix sums.
This solution calculates the running prefix sum and maintains the maximum and minimum prefix sums encountered. The maximum absolute sum is determined by the largest absolute difference between these values, which reflects the maximum absolute subarray sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), with n as the number of array elements, since the array is processed in one loop.
Space Complexity: O(1), as the solution involves a constant number of variables.
| Approach | Complexity |
|---|---|
| Modified Kadane's Algorithm | Time Complexity: O(n), where n is the number of elements in the array, because we only make a single pass through the array. |
| Prefix Sum and Minimum/Maximum Tracking | Time Complexity: O(n), with n as the number of array elements, since the array is processed in one loop. |
Maximum Absolute Sum of Any Subarray - Leetcode 1749 - Python • NeetCodeIO • 8,352 views views
Watch 9 more video solutions →Practice Maximum Absolute Sum of Any Subarray with our built-in code editor and test cases.
Practice on FleetCode