Find the Largest Magnitude of a Subarray Sum
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For any contiguous subarray of `nums`, take the absolute value of its sum. The empty subarray, with sum zero, is also allowed. Return the greatest such absolute value.
```cpp
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [4,-7,2,-3]
Output: 8
Explanation: The subarray [-7,2,-3] sums to -8.
```
**Example 2:**
```text
nums = [2,3,-1]
Output: 5
Explanation: The first two entries sum to 5.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `-10^4 <= nums[i] <= 10^4`.
### Clarifying Questions
Take the absolute value after summing the chosen subarray; do not sum individual absolute values.
```hint Inspect the structure
At what stage is the absolute value taken, and is an empty interval permitted?
```
### Reasoning checkpoints
- Optimize the absolute value of a contiguous subarray's complete sum.
- Cover negative and positive sums as well as the permitted empty subarray.
### Optional extensions
How could simultaneous maximum- and minimum-sum Kadane scans solve the same task?
Overview: Find the Largest Magnitude of a Subarray Sum. For any contiguous subarray of nums, take the absolute value of its sum. The empty subarray, with sum zero, is also allowed. Return the greatest such absolute value.