1749. Maximum Absolute Sum of Any Subarray
Description
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, thenabs(x) = -x
. - If
x
is a non-negative integer, thenabs(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
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ to represent the maximum value of the subarray ending with $nums[i]$, and define $g[i]$ to represent the minimum value of the subarray ending with $nums[i]$. Then the state transition equation of $f[i]$ and $g[i]$ is as follows:
$$ \begin{aligned} f[i] &= \max(f[i - 1], 0) + nums[i] \ g[i] &= \min(g[i - 1], 0) + nums[i] \end{aligned} $$
The final answer is the maximum value of $max(f[i], |g[i]|)$.
Since $f[i]$ and $g[i]$ are only related to $f[i - 1]$ and $g[i - 1]$, we can use two variables to replace the array, reducing the space complexity to $O(1)$.
Time complexity $O(n)$, space complexity $O(1)$, where $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|