Leetcode 1749. Maximum Absolute Sum of Any Subarray

Problem Explanation

You are given an integer array nums. Your task is to calculate the maximum absolute sum of any (possibly empty) subarray of nums.

To better understand the problem, let's go through an example.

Example:

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

Output: 5

Explanation: The subarray [2, 3] has an absolute sum abs(2+3) = abs(5) = 5.

Approach

To solve this problem, we can make use of dynamic programming. Specifically, we will calculate the maximum sum subarray ending at each position and the minimum sum subarray ending at each position. By iterating through the array and calculating the maximum and minimum sum subarrays, we ensure that the solution is kept in O(n) time complexity where n is the length of the input array.

Here is the basic algorithm:

1. Initialize ans, maxSum, and minSum
2. For each num in nums: a. Calculate the running maximum sum and running minimum sum ending at the current position b. Update ans with the maximum of ans, maxSum, and -minSum
3. Return ans as the final answer

Let's go through the provided example step by step.

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

1. Initialize ans = INT_MIN, maxSum = 0, minSum = 0
2. Iterate through nums:
   • At the first element (1): maxSum = max(1, 0+1) = 1 minSum = min(1, 0+1) = 1 ans = max(ans, maxSum, -minSum) = max(INT_MIN, 1, -1) = 1
   • At the second element (-3): maxSum = max(-3, 1+-3) = -2 minSum = min(-3, 1+-3) = -4 ans = max(ans, maxSum, -minSum) = max(1, -2, 4) = 4
   • At the third element (2): maxSum = max(2, -2+2) = 2 minSum = min(2, -4+2) = -2 ans = max(ans, maxSum, -minSum) = max(4, 2, 2) = 4
   • At the fourth element (3): maxSum = max(3, 2+3) = 5 minSum = min(3, -2+3) = 1 ans = max(ans, maxSum, -minSum) = max(4, 5, -1) = 5
3. Return ans = 5

Solutions

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    int maxAbsoluteSum(std::vector<int>& nums) {
8        int ans = INT_MIN;
9        int maxSum = 0;
10        int minSum = 0;
11
12        for (const int num : nums) {
13            maxSum = std::max(num, maxSum + num);
14            minSum = std::min(num, minSum + num);
15            ans = std::max({ans, maxSum, -minSum});
16        }
17
18        return ans;
19    }
20};

Java Solution

1class Solution {
2    public int maxAbsoluteSum(int[] nums) {
3        int ans = Integer.MIN_VALUE;
4        int maxSum = 0;
5        int minSum = 0;
6
7        for (int num : nums) {
8            maxSum = Math.max(num, maxSum + num);
9            minSum = Math.min(num, minSum + num);
10            ans = Math.max(ans, Math.max(maxSum, -minSum));
11        }
12
13        return ans;
14    }
15}

Python Solution

1class Solution:
2    def maxAbsoluteSum(self, nums: List[int]) -> int:
3        ans = float('-inf')
4        max_sum = 0
5        min_sum = 0
6        
7        for num in nums:
8            max_sum = max(num, max_sum + num)
9            min_sum = min(num, min_sum + num)
10            ans = max(ans, max_sum, -min_sum)
11            
12        return ans

JavaScript Solution

1class Solution {
2    maxAbsoluteSum(nums) {
3        let ans = Number.MIN_SAFE_INTEGER;
4        let maxSum = 0;
5        let minSum = 0;
6
7        for (const num of nums) {
8            maxSum = Math.max(num, maxSum + num);
9            minSum = Math.min(num, minSum + num);
10            ans = Math.max(ans, maxSum, -minSum);
11        }
12
13        return ans;
14    }
15}

C# Solution

1public class Solution {
2    public int MaxAbsoluteSum(int[] nums) {
3        int ans = int.MinValue;
4        int maxSum = 0;
5        int minSum = 0;
6
7        foreach (int num in nums) {
8            maxSum = Math.Max(num, maxSum + num);
9            minSum = Math.Min(num, minSum + num);
10            ans = Math.Max(ans, Math.Max(maxSum, -minSum));
11        }
12
13        return ans;
14    }
15}
16```## Further Explanation
17
18The provided solutions have a time complexity of O(n) and a space complexity of O(1) for each of the language implementations since the solutions iterate the input array using a single for loop, updating variables in place. The algorithm is efficient in both time and space, making it an appropriate approach for solving the problem. Moreover, the dynamic programming technique ensures the solutions are optimal at each iteration, eventually leading to the correct answer for the given input. It is a highly efficient solution that can handle large inputs without running into performance issues.
19
20## Time Complexity
21
22T(n) = O(n)
23
24## Space Complexity
25
26S(n) = O(1)