Maximum Absolute Sum Of Any Subarray - Leetcode Solution

Problem Statement:

Given an integer array nums, find the maximum absolute sum of any contiguous subarray of nums.

A subarray is a contiguous sequence of elements within an array.

Example:

Input: nums = [1,-3,2,3,-4] Output: 9 Explanation: The contiguous subarray [2,3] has the largest absolute sum = 5

Solution:

Approach: The brute force approach would be to take all possible subarrays and find the sum of the absolute values of their elements. However, this approach will take a lot of time for large arrays. Therefore, a more efficient approach is required.

We can use the Kadane’s algorithm to solve this problem. Kadane’s algorithm is used to find the maximum subarray sum. However, since we want to find the absolute sum, we need to modify the algorithm slightly.

Kadane’s algorithm keeps track of the maximum sum till the current index. We can modify this to keep track of the maximum absolute sum at the current index. We can do this by storing two values: the maximum absolute sum till the current index and the minimum absolute sum till the current index.

We can then return the maximum value of these two values.

Algorithm:

1. Initialize max_abs_sum and min_abs_sum to the first element of the array.
2. Initialize max_sum and min_sum to the first element of the array.
3. Iterate through the array starting from the second element.
4. Calculate the maximum absolute sum till the current index as max(max_abs_sum + nums[i], |nums[i]|).
5. Calculate the minimum absolute sum till the current index as min(min_abs_sum + nums[i], -|nums[i]|).
6. Calculate the maximum sum till the current index as max(max_sum + nums[i], nums[i]).
7. Calculate the minimum sum till the current index as min(min_sum + nums[i], nums[i]).
8. Update max_abs_sum as the maximum of max_abs_sum and min_abs_sum.
9. Update min_abs_sum as the minimum of max_abs_sum and min_abs_sum.
10. Return the maximum of max_abs_sum and max_sum.

Code:

The C++ implementation of the above algorithm is provided below:

class Solution { public: int maxAbsoluteSum(vector<int>& nums) { int n = nums.size(); int max_abs_sum = nums[0], min_abs_sum = nums[0]; int max_sum = nums[0], min_sum = nums[0];

    for (int i = 1; i < n; i++) {
        max_abs_sum = max(max_abs_sum + nums[i], abs(nums[i]));
        min_abs_sum = min(min_abs_sum + nums[i], -abs(nums[i]));
        max_sum = max(max_sum + nums[i], nums[i]);
        min_sum = min(min_sum + nums[i], nums[i]);
    }
    
    return max(max_abs_sum, max_sum);
}

};

Time Complexity: The time complexity of the above algorithm is O(n), where n is the size of the given array. This is because we only iterate through the given array once.

Space Complexity: The space complexity of the above algorithm is O(1), as we only use a constant amount of extra space to store the current maximum and minimum absolute and non-absolute sums.

1