{"id":8065,"date":"2021-02-06T08:24:40","date_gmt":"2021-02-06T16:24:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8065"},"modified":"2021-02-06T08:25:13","modified_gmt":"2021-02-06T16:25:13","slug":"leetcode-1749-maximum-absolute-sum-of-any-subarray","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1749-maximum-absolute-sum-of-any-subarray\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1749. Maximum Absolute Sum of Any Subarray"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>nums<\/code>. The&nbsp;<strong>absolute sum<\/strong>&nbsp;of a subarray&nbsp;<code>[nums<sub>l<\/sub>, nums<sub>l+1<\/sub>, ..., nums<sub>r-1<\/sub>, nums<sub>r<\/sub>]<\/code>&nbsp;is&nbsp;<code>abs(nums<sub>l<\/sub>&nbsp;+ nums<sub>l+1<\/sub>&nbsp;+ ... + nums<sub>r-1<\/sub>&nbsp;+ nums<sub>r<\/sub>)<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>maximum<\/strong>&nbsp;absolute sum of any&nbsp;<strong>(possibly empty)<\/strong>&nbsp;subarray of&nbsp;<\/em><code>nums<\/code>.<\/p>\n\n\n\n<p>Note that&nbsp;<code>abs(x)<\/code>&nbsp;is defined as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If&nbsp;<code>x<\/code>&nbsp;is a negative integer, then&nbsp;<code>abs(x) = -x<\/code>.<\/li><li>If&nbsp;<code>x<\/code>&nbsp;is a non-negative integer, then&nbsp;<code>abs(x) = x<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,-3,2,3,-4]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,-5,1,-4,3,-2]\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>-10<sup>4<\/sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Prefix Sum<\/strong><\/h2>\n\n\n\n<p>ans = max{abs(prefix_sum[i] &#8211; max(prefix_sum[0:i])), abs(prefix_sum &#8211; min(prefix_sum[0:i])}<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxAbsoluteSum(vector<int>& nums) {\n    int lo = 0;\n    int hi = 0;\n    int s = 0;\n    int ans = 0;\n    for (int x : nums) {\n      s += x;\n      ans = max({ans, abs(s - lo), abs(s - hi)});\n      hi = max(hi, s);\n      lo = min(lo, s);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;nums. The&nbsp;absolute sum&nbsp;of a subarray&nbsp;[numsl, numsl+1, &#8230;, numsr-1, numsr]&nbsp;is&nbsp;abs(numsl&nbsp;+ numsl+1&nbsp;+ &#8230; + numsr-1&nbsp;+ numsr). Return&nbsp;the&nbsp;maximum&nbsp;absolute sum of any&nbsp;(possibly empty)&nbsp;subarray of&nbsp;nums.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[177,200,41],"class_list":["post-8065","post","type-post","status-publish","format-standard","hentry","category-array","tag-medium","tag-prefix-sum","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8065"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8065\/revisions"}],"predecessor-version":[{"id":8067,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8065\/revisions\/8067"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8065"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}