# Maximum Absolute Sum of Any Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-absolute-sum-of-any-subarray
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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:

* If `x` is a negative integer, then `abs(x) = -x`.
* If `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] <= 104`

# Approaches
## Brute Force with Running Sum
This approach involves iterating through all possible contiguous subarrays, calculating the sum of each one, and keeping track of the maximum absolute sum found. To avoid a third nested loop for calculating the sum, a running sum is maintained as we extend the subarray from a fixed starting point.
**Time:** O(n^2), where n is the number of elements in the input array. The nested loops lead to a quadratic number of operations. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxAbsSum` and `currentSum`.
**Pros:** Simple to understand and implement.; It is a direct translation of the problem statement.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms for larger constraints.
### Explanation
The brute-force method systematically checks every possible subarray. A subarray is defined by its start and end indices. We can use two nested loops to generate all such pairs of indices.

The outer loop (with index `i`) determines the starting point of the subarray. The inner loop (with index `j`) determines the ending point. For each starting point `i`, we initialize a `currentSum` to zero. As the inner loop progresses from `i` to the end of the array, we add the current element `nums[j]` to `currentSum`. This `currentSum` represents the sum of the subarray `nums[i...j]`.

After calculating the sum for each subarray, we find its absolute value and compare it with a variable `maxAbsSum` that stores the maximum absolute sum found so far. If the current absolute sum is greater, we update `maxAbsSum`. The initial value of `maxAbsSum` is 0, which correctly handles the case of an empty subarray.

```java
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxAbsSum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                maxAbsSum = Math.max(maxAbsSum, Math.abs(currentSum));
            }
        }
        return maxAbsSum;
    }
}
```
### Algorithm
- Initialize `maxAbsSum` to 0.
- Iterate through the array with an index `i` from `0` to `n-1` to select the starting element of the subarray.
- Inside this loop, initialize `currentSum` to 0.
- Start a nested loop with an index `j` from `i` to `n-1` to select the ending element of the subarray.
- In the inner loop, add `nums[j]` to `currentSum`.
- Update `maxAbsSum` with `max(maxAbsSum, abs(currentSum))`.
- After both loops complete, return `maxAbsSum`.

## Kadane's Algorithm for Max and Min Subarray Sum
A more efficient approach is based on the realization that the maximum absolute sum is the larger of two values: the maximum possible subarray sum and the absolute value of the minimum possible subarray sum. Both of these values can be computed in a single pass using Kadane's algorithm and its variation for the minimum sum.
**Time:** O(n), where n is the number of elements in the array. This is because we only need a single pass through the array to compute both the maximum and minimum subarray sums. · **Space:** O(1), as it only requires a few variables to keep track of the current and overall sums, irrespective of the input size.
**Pros:** Extremely efficient, with a linear time complexity.; Optimal solution for this problem.; Uses constant extra space.
**Cons:** The logic can be less intuitive than a straightforward brute-force approach, as it relies on the insight about maximum and minimum subarray sums.
### Explanation
The core idea is that `max(abs(S))` for any subarray sum `S` is equivalent to `max(max_subarray_sum, -min_subarray_sum)`. This transforms the problem into two separate, well-known problems: finding the maximum subarray sum and finding the minimum subarray sum.

Kadane's algorithm is a dynamic programming technique that solves the maximum subarray sum problem in linear time. We can adapt it to find the minimum subarray sum as well. We can perform both calculations in a single loop over the input array.

We maintain four variables:
1.  `currentMax`: The maximum sum of a subarray ending at the current element.
2.  `maxSum`: The overall maximum subarray sum found so far.
3.  `currentMin`: The minimum sum of a subarray ending at the current element.
4.  `minSum`: The overall minimum subarray sum found so far.

For each element, we update `currentMax` and `currentMin`. If `currentMax` drops below zero, we reset it to zero because a negative-sum prefix will not help in finding a larger positive sum. Similarly, if `currentMin` goes above zero, we reset it to zero as a positive-sum prefix won't help find a smaller negative sum. We continuously update the global `maxSum` and `minSum`.

Finally, the answer is `max(maxSum, -minSum)`.

```java
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = 0;
        int currentMax = 0;
        int minSum = 0;
        int currentMin = 0;

        for (int num : nums) {
            // Kadane's algorithm for maximum subarray sum
            currentMax += num;
            if (currentMax < 0) {
                currentMax = 0;
            }
            maxSum = Math.max(maxSum, currentMax);

            // Kadane's algorithm for minimum subarray sum
            currentMin += num;
            if (currentMin > 0) {
                currentMin = 0;
            }
            minSum = Math.min(minSum, currentMin);
        }

        return Math.max(maxSum, -minSum);
    }
}
```
### Algorithm
- Initialize `maxSum = 0`, `currentMax = 0`, `minSum = 0`, and `currentMin = 0`.
- Iterate through each number `num` in the `nums` array.
- To find the maximum subarray sum:
  - Add `num` to `currentMax`.
  - If `currentMax` becomes negative, reset it to `0`.
  - Update `maxSum = max(maxSum, currentMax)`.
- To find the minimum subarray sum:
  - Add `num` to `currentMin`.
  - If `currentMin` becomes positive, reset it to `0`.
  - Update `minSum = min(minSum, currentMin)`.
- After the loop, the result is `max(maxSum, -minSum)`.

# Solutions
### Java

```java
class Solution { public int maxAbsoluteSum ( int [] nums ) { int f = 0 , g = 0 ; int ans = 0 ; for ( int x : nums ) { f = Math . max ( f , 0 ) + x ; g = Math . min ( g , 0 ) + x ; ans = Math . max ( ans , Math . max ( f , Math . abs ( g ))); } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int maxAbsoluteSum(vector<int> &nums) {
    int f = 0, g = 0;
    int ans = 0;
    for (int &x : nums) {
      f = max(f, 0) + x;
      g = min(g, 0) + x;
      ans = max({ans, f, abs(g)});
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def maxAbsoluteSum ( self , nums : List [ int ]) -> int : f = g = 0 ans = 0 for x in nums : f = max ( f , 0 ) + x g = min ( g , 0 ) + x ans = max ( ans , f , abs ( g )) return ans
```