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
Solution: Prefix Sum
ans = max{abs(prefix_sum[i] – max(prefix_sum[0:i])), abs(prefix_sum – min(prefix_sum[0:i])}
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int maxAbsoluteSum(vector<int>& nums) { int lo = 0; int hi = 0; int s = 0; int ans = 0; for (int x : nums) { s += x; ans = max({ans, abs(s - lo), abs(s - hi)}); hi = max(hi, s); lo = min(lo, s); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment