<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0053. 最大子序和 ## 題目地址(53. 最大子序和) <https://leetcode-cn.com/problems/maximum-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組 nums ,找到一個具有最大和的連續子數組(子數組最少包含一個元素),返回其最大和。 示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4] 輸出: 6 解釋: 連續子數組 [4,-1,2,1] 的和最大,為 6。 進階: 如果你已經實現復雜度為 O(n) 的解法,嘗試使用更為精妙的分治法求解。 ``` ``` ## 前置知識 - [滑動窗口](https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md) - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 百度 - 字節 - 騰訊 - bloomberg - linkedin - microsoft ## 公司 - 阿里、百度、字節、騰訊 ## 思路 這道題求解連續最大子序列和,以下從時間復雜度角度分析不同的解題思路。 #### 解法一 - 暴力解 (暴力出奇跡, 噢耶!) 一般情況下,先從暴力解分析,然后再進行一步步的優化。 **原始暴力解:**(超時) 求子序列和,那么我們要知道子序列的首尾位置,然后計算首尾之間的序列和。用 2 個 for 循環可以枚舉所有子序列的首尾位置。 然后用一個 for 循環求解序列和。這里時間復雜度太高,`O(n^3)`. **復雜度分析** - 時間復雜度:O(N3)O(N ^ 3)O(N3), 其中 N 是數組長度 - 空間復雜度:O(1)O(1)O(1) #### 解法二 - 前綴和 + 暴力解 **優化暴力解:** (震驚,居然 AC 了) 在暴力解的基礎上,用前綴和我們可以優化到暴力解`O(n^2)`, 這里以空間換時間。 這里可以使用原數組表示`prefixSum`, 省空間。 求序列和可以用前綴和(`prefixSum`) 來優化,給定子序列的首尾位置`(l, r),`那么序列和 `subarraySum=prefixSum[r] - prefixSum[l - 1];`用一個全局變量`maxSum`, 比較每次求解的子序列和,`maxSum = max(maxSum, subarraySum)`. **復雜度分析** - 時間復雜度:O(N2)O(N ^ 2)O(N2), 其中 N 是數組長度 - 空間復雜度:O(N)O(N)O(N) > 如果用更改原數組表示前綴和數組,空間復雜度降為`O(1)` 但是時間復雜度還是太高,還能不能更優化。答案是可以,前綴和還可以優化到`O(n)`. #### 解法三 - 優化前綴和 - from [**@lucifer**](https://github.com/azl397985856) 我們定義函數`S(i)` ,它的功能是計算以 `0(包括 0)`開始加到 `i(包括 i)`的值。 那么 `S(j) - S(i - 1)` 就等于 從 `i` 開始(包括 i)加到 `j`(包括 j)的值。 我們進一步分析,實際上我們只需要遍歷一次計算出所有的 `S(i)`, 其中 `i = 0,1,2....,n-1。`然后我們再減去之前的`S(k)`,其中 `k = 0,1,i - 1`,中的最小值即可。 因此我們需要 用一個變量來維護這個最小值,還需要一個變量維護最大值。 **復雜度分析** - 時間復雜度:O(N)O(N)O(N), 其中 N 是數組長度 - 空間復雜度:O(1)O(1)O(1) #### 解法四 - [分治法](https://www.wikiwand.com/zh-hans/%E5%88%86%E6%B2%BB%E6%B3%95) 我們把數組`nums`以中間位置(`m`)分為左(`left`)右(`right`)兩部分. 那么有, `left = nums[0]...nums[m - 1]` 和 `right = nums[m + 1]...nums[n-1]` 最大子序列和的位置有以下三種情況: 1. 考慮中間元素`nums[m]`, 跨越左右兩部分,這里從中間元素開始,往左求出后綴最大,往右求出前綴最大, 保持連續性。 2. 不考慮中間元素,最大子序列和出現在左半部分,遞歸求解左邊部分最大子序列和 3. 不考慮中間元素,最大子序列和出現在右半部分,遞歸求解右邊部分最大子序列和 分別求出三種情況下最大子序列和,三者中最大值即為最大子序列和。 舉例說明,如下圖: ![](https://img.kancloud.cn/fe/bd/febdefc163188ac8595adaa1024b6b85_1440x1080.jpg) **復雜度分析** - 時間復雜度:O(NlogN)O(NlogN)O(NlogN), 其中 N 是數組長度 - 空間復雜度:O(logN)O(logN)O(logN) #### 解法五 - [動態規劃](https://www.wikiwand.com/zh-hans/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92) 動態規劃的難點在于找到狀態轉移方程, `dp[i] - 表示到當前位置 i 的最大子序列和` 狀態轉移方程為: `dp[i] = max(dp[i - 1] + nums[i], nums[i])` 初始化:`dp[0] = nums[0]` 從狀態轉移方程中,我們只關注前一個狀態的值,所以不需要開一個數組記錄位置所有子序列和,只需要兩個變量, `currMaxSum - 累計最大和到當前位置i` `maxSum - 全局最大子序列和`: - `currMaxSum = max(currMaxSum + nums[i], nums[i])` - `maxSum = max(currMaxSum, maxSum)` 如圖: ![](https://img.kancloud.cn/ae/b9/aeb9fd02fead002400112ea8679e9f9a_919x614.jpg) **復雜度分析** - 時間復雜度:O(N)O(N)O(N), 其中 N 是數組長度 - 空間復雜度:O(1)O(1)O(1) ## 關鍵點分析 1. 暴力解,列舉所有組合子序列首尾位置的組合,求解最大的子序列和, 優化可以預先處理,得到前綴和 2. 分治法,每次從中間位置把數組分為左右中三部分, 分別求出左右中(這里中是包括中間元素的子序列)最大和。對左右分別深度遞歸,三者中最大值即為當前最大子序列和。 3. 動態規劃,找到狀態轉移方程,求到當前位置最大和。 ## 代碼 (`Java/Python3/Javascript`) #### 解法二 - 前綴和 + 暴力 *Java code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaximumSubarrayPrefixSum</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">int</span> len = nums.length; <span class="hljs-keyword">int</span> maxSum = Integer.MIN_VALUE; <span class="hljs-keyword">int</span> sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < len; i++) { sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i; j < len; j++) { sum += nums[j]; maxSum = Math.max(maxSum, sum); } } <span class="hljs-keyword">return</span> maxSum; } } ``` ``` *Python3 code*`(TLE)` ``` <pre class="calibre18">``` <span class="hljs-keyword">import</span> sys <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n = len(nums) maxSum = -sys.maxsize sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n): sum += nums[j] maxSum = max(maxSum, sum) <span class="hljs-keyword">return</span> maxSum ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">LSS</span>(<span class="hljs-params">list</span>) </span>{ <span class="hljs-keyword">const</span> len = list.length; <span class="hljs-keyword">let</span> max = -<span class="hljs-params">Number</span>.MAX_VALUE; <span class="hljs-keyword">let</span> sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < len; i++) { sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = i; j < len; j++) { sum += list[j]; <span class="hljs-keyword">if</span> (sum > max) { max = sum; } } } <span class="hljs-keyword">return</span> max; } ``` ``` #### 解法三 - 優化前綴和 *Java code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaxSumSubarray</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSubArray3</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">int</span> maxSum = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">int</span> sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> minSum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> num : nums) { <span class="hljs-title">// prefix Sum</span> sum += num; <span class="hljs-title">// update maxSum</span> maxSum = Math.max(maxSum, sum - minSum); <span class="hljs-title">// update minSum</span> minSum = Math.min(minSum, sum); } <span class="hljs-keyword">return</span> maxSum; } } ``` ``` *Python3 code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n = len(nums) maxSum = nums[<span class="hljs-params">0</span>] minSum = sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): sum += nums[i] maxSum = max(maxSum, sum - minSum) minSum = min(minSum, sum) <span class="hljs-keyword">return</span> maxSum ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">LSS</span>(<span class="hljs-params">list</span>) </span>{ <span class="hljs-keyword">const</span> len = list.length; <span class="hljs-keyword">let</span> max = list[<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> min = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < len; i++) { sum += list[i]; <span class="hljs-keyword">if</span> (sum - min > max) max = sum - min; <span class="hljs-keyword">if</span> (sum < min) { min = sum; } } <span class="hljs-keyword">return</span> max; } ``` ``` #### 解法四 - 分治法 *Java code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaximumSubarrayDivideConquer</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSubArrayDividConquer</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">if</span> (nums == <span class="hljs-keyword">null</span> || nums.length == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">return</span> helper(nums, <span class="hljs-params">0</span>, nums.length - <span class="hljs-params">1</span>); } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">helper</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r)</span> </span>{ <span class="hljs-keyword">if</span> (l > r) <span class="hljs-keyword">return</span> Integer.MIN_VALUE; <span class="hljs-keyword">int</span> mid = (l + r) >>> <span class="hljs-params">1</span>; <span class="hljs-keyword">int</span> left = helper(nums, l, mid - <span class="hljs-params">1</span>); <span class="hljs-keyword">int</span> right = helper(nums, mid + <span class="hljs-params">1</span>, r); <span class="hljs-keyword">int</span> leftMaxSum = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> sum = <span class="hljs-params">0</span>; <span class="hljs-title">// left surfix maxSum start from index mid - 1 to l</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = mid - <span class="hljs-params">1</span>; i >= l; i--) { sum += nums[i]; leftMaxSum = Math.max(leftMaxSum, sum); } <span class="hljs-keyword">int</span> rightMaxSum = <span class="hljs-params">0</span>; sum = <span class="hljs-params">0</span>; <span class="hljs-title">// right prefix maxSum start from index mid + 1 to r</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = mid + <span class="hljs-params">1</span>; i <= r; i++) { sum += nums[i]; rightMaxSum = Math.max(sum, rightMaxSum); } <span class="hljs-title">// max(left, right, crossSum)</span> <span class="hljs-keyword">return</span> Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right)); } } ``` ``` *Python3 code* ``` <pre class="calibre18">``` <span class="hljs-keyword">import</span> sys <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> <span class="hljs-keyword">return</span> self.helper(nums, <span class="hljs-params">0</span>, len(nums) - <span class="hljs-params">1</span>) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(self, nums, l, r)</span>:</span> <span class="hljs-keyword">if</span> l > r: <span class="hljs-keyword">return</span> -sys.maxsize mid = (l + r) // <span class="hljs-params">2</span> left = self.helper(nums, l, mid - <span class="hljs-params">1</span>) right = self.helper(nums, mid + <span class="hljs-params">1</span>, r) left_suffix_max_sum = right_prefix_max_sum = <span class="hljs-params">0</span> sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> reversed(range(l, mid)): sum += nums[i] left_suffix_max_sum = max(left_suffix_max_sum, sum) sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(mid + <span class="hljs-params">1</span>, r + <span class="hljs-params">1</span>): sum += nums[i] right_prefix_max_sum = max(right_prefix_max_sum, sum) cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid] <span class="hljs-keyword">return</span> max(cross_max_sum, left, right) ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">list, m, n</span>) </span>{ <span class="hljs-keyword">if</span> (m === n) <span class="hljs-keyword">return</span> list[m]; <span class="hljs-keyword">let</span> sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> lmax = -<span class="hljs-params">Number</span>.MAX_VALUE; <span class="hljs-keyword">let</span> rmax = -<span class="hljs-params">Number</span>.MAX_VALUE; <span class="hljs-keyword">const</span> mid = ((n - m) >> <span class="hljs-params">1</span>) + m; <span class="hljs-keyword">const</span> l = helper(list, m, mid); <span class="hljs-keyword">const</span> r = helper(list, mid + <span class="hljs-params">1</span>, n); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = mid; i >= m; i--) { sum += list[i]; <span class="hljs-keyword">if</span> (sum > lmax) lmax = sum; } sum = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = mid + <span class="hljs-params">1</span>; i <= n; i++) { sum += list[i]; <span class="hljs-keyword">if</span> (sum > rmax) rmax = sum; } <span class="hljs-keyword">return</span> <span class="hljs-params">Math</span>.max(l, r, lmax + rmax); } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">LSS</span>(<span class="hljs-params">list</span>) </span>{ <span class="hljs-keyword">return</span> helper(list, <span class="hljs-params">0</span>, list.length - <span class="hljs-params">1</span>); } ``` ``` #### 解法五 - 動態規劃 *Java code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaximumSubarrayDP</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">int</span> currMaxSum = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">int</span> maxSum = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">1</span>; i < nums.length; i++) { currMaxSum = Math.max(currMaxSum + nums[i], nums[i]); maxSum = Math.max(maxSum, currMaxSum); } <span class="hljs-keyword">return</span> maxSum; } } ``` ``` *Python3 code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubArray</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n = len(nums) max_sum_ending_curr_index = max_sum = nums[<span class="hljs-params">0</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i]) max_sum = max(max_sum_ending_curr_index, max_sum) <span class="hljs-keyword">return</span> max_sum ``` ``` *Javascript code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">LSS</span>(<span class="hljs-params">list</span>) </span>{ <span class="hljs-keyword">const</span> len = list.length; <span class="hljs-keyword">let</span> max = list[<span class="hljs-params">0</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < len; i++) { list[i] = <span class="hljs-params">Math</span>.max(<span class="hljs-params">0</span>, list[i - <span class="hljs-params">1</span>]) + list[i]; <span class="hljs-keyword">if</span> (list[i] > max) max = list[i]; } <span class="hljs-keyword">return</span> max; } ``` ``` ## 擴展 - 如果數組是二維數組,求最大子數組的和? - 如果要求最大子序列的乘積? ## 相似題 - [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) - [Longest Turbulent Subarray](https://leetcode.com/problems/longest-turbulent-subarray/) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看