專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友收到一個offer，因為自己在洗澡沒有看到，結果過了40分鐘hr又把offer給撤回了，關鍵hr還把他的聯系方式給刪了，也沒辦法爭取了。

我對這種僅過了40分鐘就撤回offer的行為很是不能理解，說明他們也不是真的很缺人，如果真的缺人，也不會在乎那幾十分鐘，所以不去也挺好。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1186題：刪除一次得到子數組最大和，難度是中等。

給你一個整數數組，返回它的某個非空子數組（連續元素）在執行一次可選的刪除操作后，所能得到的最大元素總和。換句話說，你可以從原數組中選出一個子數組，并可以決定要不要從中刪除一個元素（只能刪一次哦），（刪除后）子數組中至少應當有一個元素，然后該子數組（剩下）的元素總和是所有子數組之中最大的。

示例1：

輸入：arr = [1,-2,0,3] 輸出：4 解釋：我們可以選出 [1, -2, 0, 3]，然后刪掉 -2，這樣得到 [1, 0, 3]，和最大。

示例2：

輸入：arr = [1,-2,0,3] 輸出：4 解釋：我們可以選出 [1, -2, 0, 3]，然后刪掉 -2，這樣得到 [1, 0, 3]，和最大。

• 1 <= arr.length <= 10^5

• -10^4 <= arr[i] <= 10^4

問題分析

這題說的是從原數組中最多刪除一個元素，然后求最大連續子數組的和，實際上這是一道動態規劃的問題。

我們定義dp[i][0]表示沒有刪除任何元素且以arr[i]為結尾的最大連續子數組之和。dp[i][1]表示最多刪除一個元素且以arr[i]為結尾的最大連續子數組之和，刪除前以arr[i]為結尾的也算。最后保存最大值即可。

很明顯我們可以得出：

dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];

dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);

dp[i][0]表示沒有刪除任何元素，以它結尾的最大連續子數組之和是它自己arr[i]加上它前面的連續子數組之和，如果它前面的連續子數組之和為負數，就不要加了 。

dp[i][1]表示最多刪除一個元素，也可能是之前就已經刪除過，所以我們取dp[i - 1][1] + arr[i]，也可能是之前沒有刪除過，而是把當前的元素arr[i]給刪除了，我們取 dp[i - 1][0]，這兩種情況我們取最大值即可。

動態規劃有了遞推公式就簡單了，我們在看下Base Case，第一個元素如果沒有刪除，則dp[0][0] = arr[0]；如果刪除了，則dp[0][1] = 0。

JAVA：

public int maximumSum(int[] arr) {     int n = arr.length;     int[][] dp = new int[n][2];     dp[0][0] = arr[0];// 第一個元素沒有刪除     dp[0][1] = 0;// 第二個元素被刪除     int ans = arr[0];// 保存最大值。     for (int i = 1; i < arr.length; i++) {         dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];         dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);         ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));     }     return ans; }

C++：

public:     int maximumSum(vector

 &arr) {         int n = arr.size();         vector

 > dp(n, vector

 (2, 0));         dp[0][0] = arr[0];// 第一個元素沒有刪除         dp[0][1] = 0;// 第二個元素被刪除         int ans = arr[0];// 保存最大值。         for (int i = 1; i < n; i++) {             dp[i][0] = max(dp[i - 1][0], 0) + arr[i];             dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]);             ans = max(ans, max(dp[i][0], dp[i][1]));         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。