專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近一網(wǎng)友收到一個offer，因為自己在洗澡沒有看到，結(jié)果過了40分鐘hr又把offer給撤回了，關(guān)鍵hr還把他的聯(lián)系方式給刪了，也沒辦法爭取了。
我對這種僅過了40分鐘就撤回offer的行為很是不能理解，說明他們也不是真的很缺人，如果真的缺人，也不會在乎那幾十分鐘，所以不去也挺好。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1186題：刪除一次得到子數(shù)組最大和，難度是中等。
給你一個整數(shù)數(shù)組，返回它的某個非空子數(shù)組（連續(xù)元素）在執(zhí)行一次可選的刪除操作后，所能得到的最大元素總和。換句話說，你可以從原數(shù)組中選出一個子數(shù)組，并可以決定要不要從中刪除一個元素（只能刪一次哦），（刪除后）子數(shù)組中至少應(yīng)當(dāng)有一個元素，然后該子數(shù)組（剩下）的元素總和是所有子數(shù)組之中最大的。
示例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
問題分析
這題說的是從原數(shù)組中最多刪除一個元素，然后求最大連續(xù)子數(shù)組的和，實際上這是一道動態(tài)規(guī)劃的問題。
我們定義dp[i][0]表示沒有刪除任何元素且以arr[i]為結(jié)尾的最大連續(xù)子數(shù)組之和。dp[i][1]表示最多刪除一個元素且以arr[i]為結(jié)尾的最大連續(xù)子數(shù)組之和，刪除前以arr[i]為結(jié)尾的也算。最后保存最大值即可。
很明顯我們可以得出：
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]表示沒有刪除任何元素，以它結(jié)尾的最大連續(xù)子數(shù)組之和是它自己arr[i]加上它前面的連續(xù)子數(shù)組之和，如果它前面的連續(xù)子數(shù)組之和為負(fù)數(shù)，就不要加了 。
dp[i][1]表示最多刪除一個元素，也可能是之前就已經(jīng)刪除過，所以我們?nèi)p[i - 1][1] + arr[i]，也可能是之前沒有刪除過，而是把當(dāng)前的元素arr[i]給刪除了，我們?nèi)?dp[i - 1][0]，這兩種情況我們?nèi)?a class="keyword-search" >最大值即可。
動態(tài)規(guī)劃有了遞推公式就簡單了，我們在看下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; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼