數(shù)組系列
力扣數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組-00-概覽
力扣.53 最大子數(shù)組和 maximum-subarray
力扣.128 最長連續(xù)系列 longest-consecutive-sequence
力扣.167 兩數(shù)之和 II two-sum-ii
力扣.170 兩數(shù)之和 III two-sum-iii
力扣.653 兩數(shù)之和 IV two-sum-IV
題目
給你一個(gè)整數(shù)數(shù)組 nums ，請你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
子數(shù)組是數(shù)組中的一個(gè)連續(xù)部分。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。
示例 2：
輸入：nums = [1]
輸出：1
示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23
提示：
1 <= nums.length <= 10^5
-104 <= nums[i] <= 10^4
進(jìn)階：如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解。
v1-前綴和 BF
思路
看到連續(xù)子數(shù)組和，比較自然的是想到用前綴和來加速子數(shù)組和的計(jì)算。
1）構(gòu)建好前綴和
2）窮舉所有可能的子數(shù)組和，找出最大值。
實(shí)現(xiàn)
class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
int[] prefixSum = new int[n];
prefixSum[0] = nums[0];
for(int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i-1] + nums[i];
}
// BF 匹配
int maxSum = nums[0];
for(int i = 0; i < n; i++) {
// 后面的數(shù)組 》 前一個(gè)標(biāo)識
for(int j = i; j < n; j++) {
int sum = prefixSum[j] - prefixSum[i] + nums[i];
// 更新最大值
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
}
效果
超出時(shí)間限制
204 / 210 個(gè)通過的測試用例
v2-如何改進(jìn)? 雙指針？
思路
我們之所以很慢，是因?yàn)樵谟?jì)算連續(xù)子數(shù)組和的時(shí)候，計(jì)算了各種場景。但是這里要如何優(yōu)化呢？
但是不對比所有的，如何找到最大的呢？
最氣人的是題目中的那一句：如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解。
左右兩邊的雙指針可行嗎？
感覺雙指針不可行 雙指針適合計(jì)算最大的長度，但是不太適合這種最大的和。
v3-貪心
思路1
看了一眼相似題目，其中有一個(gè)是 【買賣股票的最佳時(shí)機(jī)】{簡單}
于是貪心的話，思路可以簡化為：
public int maxSubArray(int[] nums) {
final int n = nums.length;
// BF 匹配
int maxSum = nums[0];
for(int i = 1; i < n; i++) {
// 加上當(dāng)前值變大？不加當(dāng)前值？
// 變大
int num = nums[i];
// 無腦直接加
if(num >= 0) {
maxSum += num;
} else {
// 如果不是呢？
// 也不能貿(mào)然丟棄 因?yàn)檫B續(xù)起來，后來可能又大于0的？
// 那么 怎么簡單的判斷這個(gè)事情呢？
}
}
return maxSum;
}
思路-打開評論區(qū)
首先看到一首打油詩 被逗笑了
打開我的題庫，調(diào)為簡單難度。
計(jì)算最大子數(shù)，直接給我難住。
報(bào)錯(cuò)鋪滿屏幕，凝望沒有思路。
縫縫補(bǔ)補(bǔ)做出，擊敗零個(gè)用戶。
翻閱評論找補(bǔ)，令我勃然大怒。
不禁心有一問，都是人，憑什么我——這么廢物。
55555555
被打開的不單單是評論區(qū)的，當(dāng)然還有自己的思路。
我們整體的方向沒錯(cuò)，但是這里需要一個(gè)技巧。
如下：
/**解題思路
用 temp 記錄局部最優(yōu)值，用 result 記錄全局最優(yōu)值。
每遍歷一個(gè)新元素時(shí)，判斷（已遍歷的連續(xù)子數(shù)組的和）加上（當(dāng)前元素值），與（當(dāng)前元素值）對比誰更大。
（1）如果已遍歷的連續(xù)子數(shù)組的和 + 當(dāng)前元素值 >= 當(dāng)前元素值
說明（已遍歷的連續(xù)子數(shù)組的和）是大于等于0的，令 temp = 已遍歷的連續(xù)子數(shù)組的和 + 當(dāng)前元素值。
（2）如果已遍歷的連續(xù)子數(shù)組的和 + 當(dāng)前元素值 < 當(dāng)前元素值
說明（已遍歷的連續(xù)子數(shù)組的和）是小于0的，加上這部分只會(huì)拖累當(dāng)前元素，故應(yīng)該直接拋棄掉這部分，令 * temp = 當(dāng)前元素值。
（3）對比 temp 和 result，如果 temp 更大，則更新到 result 中。
*/
代碼
class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
// BF 匹配
int maxSum = nums[0];
int tempSum = nums[0];
for(int i = 1; i < n; i++) {
int num = nums[i];
// 歷史數(shù)據(jù)大于等于0，則保留繼續(xù)累加
if(tempSum >= 0) {
tempSum += num;
} else {
// 歷史和小于 0，直接舍棄。只保留今天
tempSum = num;
}
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
}
簡單的優(yōu)化，我們直接判斷是否大于等于0即可，減少一次累加計(jì)算。聊勝于無。
效果
1ms 100%
效果拔群
小結(jié)
那么這一題和股票有啥關(guān)系呢？
股票的買賣貪心其實(shí)要簡單一些，就是明天比今天高，直接無腦買賣。而且不要求連續(xù)。
這里要求連續(xù)，就需要一個(gè)巧妙的構(gòu)思，有時(shí)候不一定能很快想到。
比如我們可買賣股票無限次數(shù)上點(diǎn)難度，增加一個(gè)限制，買賣的天數(shù)必須是連續(xù)的天數(shù)，怎么解？
其實(shí)就是 {買+賣} 的和當(dāng)做一個(gè)數(shù)，然后就變成這一題了
v3-DP
思路
一個(gè)問題能不能被 DP 解決呢？
就看能不能拆分為遞推的子問題。
那么，這個(gè)問題可以嗎?
遞推公式是什么？
也就是我們還是需要想到上面那個(gè)思路。
dp[i] = Math.max(0, dp[i-1]) + nums[i];
實(shí)現(xiàn)
class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int maxResult = nums[0];
for(int i = 1; i < n; i++) {
int num = nums[i];
dp[i] = Math.max(0, dp[i-1]) + nums[i];
maxResult = Math.max(dp[i], maxResult);
}
return maxResult;
}
}
效果
2ms 36.91%
小結(jié)
DP 的優(yōu)點(diǎn)是使用范圍更加廣泛，這如果是一個(gè)系列的題目，不斷上難度，DP 也許可以成為一個(gè)模板。
但是如果是性能，比不上上面的 greedy。
或者說上面的貪心，是對下面遞推數(shù)組的存儲(chǔ)空間優(yōu)化。
差點(diǎn)掛在了第一個(gè)選擇的數(shù)組題目上....ORZ
