# 1186. 刪除一次得到子數組最大和 ## 題目地址(1186. 刪除一次得到子數組最大和) <https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個整數數組，返回它的某個 非空 子數組（連續元素）在執行一次可選的刪除操作后，所能得到的最大元素總和。 換句話說，你可以從原數組中選出一個子數組，并可以決定要不要從中刪除一個元素（只能刪一次哦），（刪除后）子數組中至少應當有一個元素，然后該子數組（剩下）的元素總和是所有子數組之中最大的。 注意，刪除一個元素后，子數組 不能為空。 請看示例： 示例 1： 輸入：arr = [1,-2,0,3] 輸出：4 解釋：我們可以選出 [1, -2, 0, 3]，然后刪掉 -2，這樣得到 [1, 0, 3]，和最大。 示例 2： 輸入：arr = [1,-2,-2,3] 輸出：3 解釋：我們直接選出 [3]，這就是最大和。 示例 3： 輸入：arr = [-1,-1,-1,-1] 輸出：-1 解釋：最后得到的子數組不能為空，所以我們不能選擇 [-1] 并從中刪去 -1 來得到 0。 我們應該直接選擇 [-1]，或者選擇 [-1, -1] 再從中刪去一個 -1。 提示： 1 <= arr.length <= 10^5 -10^4 <= arr[i] <= 10^4 ``` ``` ## 前置知識 - 數組 - 動態規劃 ## 公司 - 字節 ## 思路 ### 暴力法 符合知覺的做法是求出所有的情況，然后取出最大的。 我們只需要兩層循環接口，外循環用于確定我們丟棄的元素，內循環用于計算subArraySum。 ``` <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">maximumSum</span><span class="hljs-params">(self, arr: List[int])</span> -> int:</span> res = arr[<span class="hljs-params">0</span>] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubSum</span><span class="hljs-params">(arr, skip)</span>:</span> res = maxSub = float(<span class="hljs-string">"-inf"</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(arr)): <span class="hljs-keyword">if</span> i == skip: <span class="hljs-keyword">continue</span> maxSub = max(arr[i], maxSub + arr[i]) res = max(res, maxSub) <span class="hljs-keyword">return</span> res <span class="hljs-title"># 這里循環到了len(arr)項，表示的是一個都不刪除的情況</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(arr) + <span class="hljs-params">1</span>): res = max(res, maxSubSum(arr, i)) <span class="hljs-keyword">return</span> res ``` ``` ### 空間換時間 上面的做法在LC上會TLE， 因此我們需要換一種思路，既然超時了，我們是否可以從空間換時間的角度思考呢？我們可以分別從頭尾遍歷，建立兩個subArraySub的數組l和r。 其實這個不難想到，很多題目都用到了這個技巧。 具體做法： - 一層遍歷， 建立l數組，l\[i\]表示從左邊開始的以arr\[i\]結尾的subArraySum的最大值 - 一層遍歷， 建立r數組，r\[i\]表示從右邊開始的以arr\[i\]結尾的subArraySum的最大值 - 一層遍歷， 計算 l\[i - 1\] + r\[i + 1\] 的最大值 > l\[i - 1\] + r\[i + 1\]的含義就是刪除arr\[i\]的子數組最大值 - 上面的這個步驟得到了刪除一個的子數組最大值， 不刪除的只需要在上面循環順便計算一下即可 ``` <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">maximumSum</span><span class="hljs-params">(self, arr: List[int])</span> -> int:</span> n = len(arr) l = [arr[<span class="hljs-params">0</span>]] * n r = [arr[n - <span class="hljs-params">1</span>]] * n <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> arr[<span class="hljs-params">0</span>] res = arr[<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): l[i] = max(l[i - <span class="hljs-params">1</span>] + arr[i], arr[i]) res = max(res, l[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">2</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): r[i] = max(r[i + <span class="hljs-params">1</span>] + arr[i], arr[i]) res = max(res, r[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n - <span class="hljs-params">1</span>): res = max(res, l[i - <span class="hljs-params">1</span>] + r[i + <span class="hljs-params">1</span>]) <span class="hljs-keyword">return</span> res ``` ``` ### 動態規劃 上面的算法雖然時間上有所改善，但是正如標題所說，空間復雜度是O(n),有沒有辦法改進呢？答案是使用動態規劃。 具體過程： - 定義max0，表示以arr\[i\]結尾且一個都不漏的最大子數組和 - 定義max1，表示以arr\[i\]或者arr\[i - 1\]結尾，可以漏一個的最大子數組和 - 遍歷數組，更新max1和max0（注意先更新max1，因為max1用到了上一個max0） - 其中`max1 = max(max1 + arr[i], max0)`, 即刪除arr\[i - 1\]或者刪除arr\[i\] - 其中`max0 = max(max0 + arr[i], arr[i])`， 一個都不刪除 ``` <pre class="calibre18">``` <span class="hljs-title">#</span> <span class="hljs-title"># @lc app=leetcode.cn id=1186 lang=python3</span> <span class="hljs-title">#</span> <span class="hljs-title"># [1186] 刪除一次得到子數組最大和</span> <span class="hljs-title">#</span> <span class="hljs-title"># @lc code=start</span> <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">maximumSum</span><span class="hljs-params">(self, arr: List[int])</span> -> int:</span> <span class="hljs-title"># DP</span> max0 = arr[<span class="hljs-params">0</span>] max1 = arr[<span class="hljs-params">0</span>] res = arr[<span class="hljs-params">0</span>] n = len(arr) <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> max0 <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): <span class="hljs-title"># 先更新max1，再更新max0，因為max1用到了上一個max0</span> max1 = max(max1 + arr[i], max0) max0 = max(max0 + arr[i], arr[i]) res = max(res, max0, max1) <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 關鍵點解析 - 空間換時間 - 頭尾雙數組 - 動態規劃 ## 相關題目 - [42.trapping-rain-water](42.trapping-rain-water.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。