# 1031. 兩個非重疊子數組的最大和 ## 題目地址(1031. 兩個非重疊子數組的最大和) <https://leetcode-cn.com/problems/maximum-sum-of-two-non-overlapping-subarrays/> ## 題目描述 ``` <pre class="calibre18">``` 給出非負整數數組 A ，返回兩個非重疊（連續）子數組中元素的最大和，子數組的長度分別為 L 和 M。（這里需要澄清的是，長為 L 的子數組可以出現在長為 M 的子數組之前或之后。） 從形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并滿足下列條件之一： 0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或 0 <= j < j + M - 1 < i < i + L - 1 < A.length. 示例 1： 輸入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 輸出：20 解釋：子數組的一種選擇中，[9] 長度為 1，[6,5] 長度為 2。 示例 2： 輸入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 輸出：29 解釋：子數組的一種選擇中，[3,8,1] 長度為 3，[8,9] 長度為 2。 示例 3： 輸入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 輸出：31 解釋：子數組的一種選擇中，[5,6,0,9] 長度為 4，[0,3,8] 長度為 3。 提示： L >= 1 M >= 1 L + M <= A.length <= 1000 0 <= A[i] <= 1000 ``` ``` ## 前置知識 - 數組 ## 公司 - 字節 ## 思路(動態規劃) 題目中要求在前N(數組長度)個數中找出長度分別為L和M的非重疊子數組之和的最大值, 因此, 我們可以定義數組A中前i個數可構成的非重疊子數組L和M的最大值為SUMM\[i\], 并找到SUMM\[i\]和SUMM\[i-1\]的關系, 那么最終解就是SUMM\[N\]. 以下為圖解:  ## 關鍵點解析 1. 注意圖中描述的都是A\[i-1\], 而不是A\[i\], 因為base case為空數組, 而不是A\[0\]; 2. 求解圖中ASUM數組的時候, 注意定義的是ASUM\[i\] = sum(A\[0:i\]), 因此當i等于0時, A\[0:0\]為空數組, 即: ASUM\[0\]為0, 而ASUM\[1\]才等于A\[0\]; 3. 求解圖中MAXL數組時, 注意i < L時, 沒有意義, 因為長度不夠, 所以從i = L時才開始求解; 4. 求解圖中MAXM數組時, 也一樣, 要從i = M時才開始求解; 5. 求解圖中SUMM數組時, 因為我們需要一個L子數組和一個M子數組, 因此長度要大于等于L+M才有意義, 所以要從i = L + M時開始求解. ## 代碼 - 語言支持: Python Python 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">maxSumTwoNoOverlap</span><span class="hljs-params">(self, a: List[int], l: int, m: int)</span> -> int:</span> <span class="hljs-string">""" define asum[i] as the sum of subarray, a[0:i] define maxl[i] as the maximum sum of l-length subarray in a[0:i] define maxm[i] as the maximum sum of m-length subarray in a[0:i] define msum[i] as the maximum sum of non-overlap l-length subarray and m-length subarray case 1: a[i] is both not in l-length subarray and m-length subarray, then msum[i] = msum[i - 1] case 2: a[i] is in l-length subarray, then msum[i] = asum[i] - asum[i-l] + maxm[i-l] case 3: a[i] is in m-length subarray, then msum[i] = asum[i] - asum[i-m] + maxl[i-m] so, msum[i] = max(msum[i - 1], asum[i] - asum[i-l] + maxl[i-l], asum[i] - asum[i-m] + maxm[i-m]) """</span> alen, tlen = len(a), l + m asum = [<span class="hljs-params">0</span>] * (alen + <span class="hljs-params">1</span>) maxl = [<span class="hljs-params">0</span>] * (alen + <span class="hljs-params">1</span>) maxm = [<span class="hljs-params">0</span>] * (alen + <span class="hljs-params">1</span>) msum = [<span class="hljs-params">0</span>] * (alen + <span class="hljs-params">1</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(tlen): <span class="hljs-keyword">if</span> i == <span class="hljs-params">1</span>: asum[i] = a[i - <span class="hljs-params">1</span>] <span class="hljs-keyword">elif</span> i > <span class="hljs-params">1</span>: asum[i] = asum[i - <span class="hljs-params">1</span>] + a[i - <span class="hljs-params">1</span>] <span class="hljs-keyword">if</span> i >= l: maxl[i] = max(maxl[i - <span class="hljs-params">1</span>], asum[i] - asum[i - l]) <span class="hljs-keyword">if</span> i >= m: maxm[i] = max(maxm[i - <span class="hljs-params">1</span>], asum[i] - asum[i - m]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(tlen, alen + <span class="hljs-params">1</span>): asum[i] = asum[i - <span class="hljs-params">1</span>] + a[i - <span class="hljs-params">1</span>] suml = asum[i] - asum[i - l] summ = asum[i] - asum[i - m] maxl[i] = max(maxl[i - <span class="hljs-params">1</span>], suml) maxm[i] = max(maxm[i - <span class="hljs-params">1</span>], summ) msum[i] = max(msum[i - <span class="hljs-params">1</span>], suml + maxm[i - l], summ + maxl[i - m]) <span class="hljs-keyword">return</span> msum[<span class="hljs-params">-1</span>] ``` ``` ## 擴展 1. 代碼中, 求解了4個動態規劃數組來求解最終值, 有沒有可能只用兩個數組來求解該題, 可以的話, 需要保留的又是哪兩個數組? 2. 代碼中, 求解的4動態規劃數組的順序能否改變, 哪些能改, 哪些不能改? 如果采用前綴和數組的話，可以只使用O(n)的空間來存儲前綴和，O(1)的動態規劃狀態空間來完成。C++代碼如下: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxSumTwoNoOverlap</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& A, <span class="hljs-keyword">int</span> L, <span class="hljs-keyword">int</span> M)</span> </span>{ <span class="hljs-keyword">auto</span> tmp = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>{A[<span class="hljs-params">0</span>]}; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">1</span>; i < A.size(); ++i) { tmp.push_back(A[i] + tmp[i - <span class="hljs-params">1</span>]); } <span class="hljs-keyword">auto</span> res = tmp[L + M - <span class="hljs-params">1</span>], lMax = tmp[L - <span class="hljs-params">1</span>], mMax = tmp[M - <span class="hljs-params">1</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = L + M; i < tmp.size(); ++i) { lMax = max(lMax, tmp[i - M] - tmp[i - M - L]); mMax = max(mMax, tmp[i - L] - tmp[i - L - M]); res = max(res, max(lMax + tmp[i] - tmp[i - M], mMax + tmp[i] - tmp[i - L])); } <span class="hljs-keyword">return</span> res; } }; ``` ```