diff options
-rw-r--r-- | max_abs_sum_any_subarr.c | 18 | ||||
-rw-r--r-- | 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 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__": |