leetcode

commit 5afeed9d77e479ea3b576ff0c10b0d5f001cc078
parent 658556f3d4eaa1cdefd7009e7b6ccb3cabcd31ac
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 25 Feb 2025 21:16:30 -0700

1749. maximum absolute sum of any subarray (improvments)

Diffstat:
M
max_abs_sum_any_subarr.c
 | 
18
+++++-------------
M
max_abs_sum_any_subarr.py
 | 
9
++-------

2 files changed, 7 insertions(+), 20 deletions(-)
diff --git 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
@@ -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__":