<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國際加速解決方案。 廣告
                # 一文看懂《最大子序列和問題》 # 一文看懂《最大子序列和問題》 最大子序列和是一道經典的算法題, leetcode 也有原題《53.maximum-sum-subarray》,今天我們就來徹底攻克它。 ## 題目描述 求取數組中最大連續子序列和,例如給定數組為 A = \[1, 3, -2, 4, -5\], 則最大連續子序列和為 6,即 1 + 3 +(-2)+ 4 = 6。 去 首先我們來明確一下題意。 - 題目說的子數組是連續的 - 題目只需要求和,不需要返回子數組的具體位置。 - 數組中的元素是整數,但是可能是正數,負數和 0。 - 子序列的最小長度為 1。 比如: - 對于數組 \[1, -2, 3, 5, -3, 2\], 應該返回 3 + 5 = 8 - 對于數組 \[0, -2, 3, 5, -1, 2\], 應該返回 3 + 5 + -1 + 2 = 9 - 對于數組 \[-9, -2, -3, -5, -3\], 應該返回 -2 ## 解法一 - 暴力法(超時法) 一般情況下,先從暴力解分析,然后再進行一步步的優化。 ### 思路 我們來試下最直接的方法,就是計算所有的子序列的和,然后取出最大值。 記 Sum\[i,....,j\]為數組 A 中第 i 個元素到第 j 個元素的和,其中 0 <= i <= j < n, 遍歷所有可能的 Sum\[i,....,j\] 即可。 我們去枚舉以 0,1,2...n-1 開頭的所有子序列即可, 對于每一個開頭的子序列,我們都去枚舉從當前開始到 n-1 的所有情況。 這種做法的時間復雜度為 O(N^2), 空間復雜度為 O(1)。 ### 代碼 JavaScript: ``` <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: ``` <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; } } ``` ``` Python 3: ``` <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 ``` ``` 空間復雜度非常理想,但是時間復雜度有點高。怎么優化呢?我們來看下下一個解法。 ## 解法二 - 分治法 ### 思路 我們來分析一下這個問題, 我們先把數組平均分成左右兩部分。 此時有三種情況: - 最大子序列全部在數組左部分 - 最大子序列全部在數組右部分 - 最大子序列橫跨左右數組 對于前兩種情況,我們相當于將原問題轉化為了規模更小的同樣問題。 對于第三種情況,由于已知循環的起點(即中點),我們只需要進行一次循環,分別找出 左邊和右邊的最大子序列即可。 所以一個思路就是我們每次都對數組分成左右兩部分,然后分別計算上面三種情況的最大子序列和, 取出最大的即可。 舉例說明,如下圖: ![](https://img.kancloud.cn/97/05/970539c0aba68a4596261ba3dbd35d48_1440x1080.jpg)(by [snowan](https://github.com/snowan)) 這種做法的時間復雜度為 O(N\*logN), 空間復雜度為 O(1)。 ### 代碼 JavaScript: ``` <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: ``` <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)); } } ``` ``` Python 3 : ``` <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) ``` ``` ## 解法三 - 動態規劃 ### 思路 我們來思考一下這個問題, 看能不能將其拆解為規模更小的同樣問題,并且能找出 遞推關系。 我們不妨假設問題 Q(list, i) 表示 list 中以索引 i 結尾的情況下最大子序列和, 那么原問題就轉化為 Q(list, i), 其中 i = 0,1,2...n-1 中的最大值。 我們繼續來看下遞歸關系,即 Q(list, i)和 Q(list, i - 1)的關系, 即如何根據 Q(list, i - 1) 推導出 Q(list, i)。 如果已知 Q(list, i - 1), 我們可以將問題分為兩種情況,即以索引為 i 的元素終止, 或者只有一個索引為 i 的元素。 - 如果以索引為 i 的元素終止, 那么就是 Q(list, i - 1) + list\[i\] - 如果只有一個索引為 i 的元素,那么就是 list\[i\] 分析到這里,遞推關系就很明朗了,即`Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]` 舉例說明,如下圖: ![](https://img.kancloud.cn/2b/d2/2bd2628b1833f28de92d544ae5b96598_919x614.jpg)(by [snowan](https://github.com/snowan)) 這種算法的時間復雜度 O(N), 空間復雜度為 O(1) ### 代碼 JavaScript: ``` <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; } ``` ``` Java: ``` <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; } } ``` ``` Python 3: ``` <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 ``` ``` ## 解法四 - 數學分析 ### 思路 我們來通過數學分析來看一下這個題目。 我們定義函數 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(1)。 其實很多題目,都有這樣的思想, 比如之前的《每日一題 - 電梯問題》。 ### 代碼 JavaScript: ``` <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: ``` <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; } } ``` ``` Python 3: ``` <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 ``` ``` ## 總結 我們使用四種方法解決了`《最大子序列和問題》`, 并詳細分析了各個解法的思路以及復雜度,相信下次你碰到相同或者類似的問題 的時候也能夠發散思維,做到`一題多解,多題一解`。 實際上,我們只是求出了最大的和,如果題目進一步要求出最大子序列和的子序列呢? 如果要題目允許不連續呢? 我們又該如何思考和變通?如何將數組改成二維,求解最大矩陣和怎么計算? 這些問題留給讀者自己來思考。
                  <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>

                              哎呀哎呀视频在线观看