aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_abs_sum_any_subarr.c18
-rw-r--r--max_abs_sum_any_subarr.py9
2 files changed, 7 insertions, 20 deletions
diff --git a/max_abs_sum_any_subarr.c b/max_abs_sum_any_subarr.c
index 8ddd1eb..f7ae0ca 100644
--- a/max_abs_sum_any_subarr.c
+++ b/max_abs_sum_any_subarr.c
@@ -10,21 +10,13 @@
*/
int maxAbsoluteSum(int *nums, int numsSize) {
- int max_sum = INT_MIN, min_sum = INT_MAX, curr_sum = 0;
+ int total = 0, min = 0, max = 0;
for (int i = 0; i < numsSize; i++) {
- curr_sum += nums[i];
- max_sum = max_sum > curr_sum ? max_sum : curr_sum;
- if (curr_sum < 0)
- curr_sum = 0;
+ total += nums[i];
+ min = fmin(min, total);
+ max = fmax(max, total);
}
- curr_sum = 0;
- for (int i = 0; i < numsSize; i++) {
- curr_sum += nums[i];
- min_sum = min_sum < curr_sum ? min_sum : curr_sum;
- if (curr_sum > 0)
- curr_sum = 0;
- }
- return abs(max_sum) > abs(min_sum) ? abs(max_sum) : abs(min_sum);
+ return max - min;
}
int main() {
diff --git a/max_abs_sum_any_subarr.py b/max_abs_sum_any_subarr.py
index cd58866..c98f920 100644
--- a/max_abs_sum_any_subarr.py
+++ b/max_abs_sum_any_subarr.py
@@ -1,4 +1,5 @@
# 1749. Maximum Absolute Sum of Any Subarray
+from itertools import accumulate
"""
you are given an integer array 'nums'. the absolute sum of a subarray '[nums,
@@ -15,13 +16,7 @@ class Solution(object):
:type nums: List[int]
:rtype: int
"""
- n, ans = len(nums), 0
- dp = [[0, 0] for _ in range(n)]
- for i in range(n):
- dp[i][0] = min(dp[i - 1][0] + nums[i], nums[i])
- dp[i][1] = max(dp[i - 1][1] + nums[i], nums[i])
- ans = max(ans, abs(dp[i][0]), dp[i][1])
- return ans
+ return max(accumulate(nums, initial=0)) - min(accumulate(nums, initial=0))
if __name__ == "__main__":