【LeetCode】最大子序和從O(N^3)到O(N) - 暴力初探 - 分而治之 - 在線處理

語言: CN / TW / HK

theme: fancy highlight: a11y-dark


嗨!~ 大家好,我是YK菌 🐷 ,一個微系前端 ✨,愛思考,愛總結,愛記錄,愛分享 🏹,歡迎關注我呀 😘 ~ [微信號: yk2012yk2012,微信公眾號:ykyk2012]

「這是我參與11月更文挑戰的第29天,活動詳情查看:2021最後一次更文挑戰

其實這題我三年前在我的公眾號裏有寫過 分而治之方法解決最大子列和問題——還有更快 以及 最快處理最大子列和問題——在線處理 那個時候還是用的C語言,今天我們使用JavaScript來再探索一下這道題吧~ 其實解題不是目的,我們真正的目的是通過這道題,學習一些算法思想,學習一些解決問題的方法和技巧!

53. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

給定一個整數數組 nums ,找到一個具有最大和的連續子數組(子數組最少包含一個元素),返回其最大和。

① 初探:暴力求和

我們可以想到最簡單最暴力的方法,就是直接對所有子列依次求和,然後逐個比較,取最大的即為最大子列和。

```js /* * @param {number[]} nums * @return {number} / var maxSubArray = function (nums) { let thisSum = -Infinity; let maxSum = -Infinity;

for (let i = 0; i < nums.length; i++) { for (let j = i; j < nums.length; j++) { thisSum = 0; // nums[i] 到 nums[j]的子序和 for (let k = i; k <= j; k++) { thisSum += nums[k]; if (thisSum > maxSum) { // 如果剛得到的這個子列和更大 maxSum = thisSum; // 則更新結果 } } } }

return maxSum; }; ```

測試是對的

image.png

但是效率太低,無法通過所有測試用例

image.png

這裏面一共用到了三次循環,所以他的時間複雜度為 $$O(N^{3})$$

其實再仔細想想,需要全部這樣逐個求和嗎?是不是存在許多重複求和,可不可以優化一下呢?

② 進步:優化求和

我們把第三次循環進行變換, 第三次循環其實沒有必要, 直接在前面的基礎上加上後面一個元素,就可以得到新的子序和

進行改進後的代碼 ```js /* * @param {number[]} nums * @return {number} / var maxSubArray = function(nums) { let thisSum = -Infinity; let maxSum = -Infinity;

for (let i = 0; i < nums.length; i++) { thisSum = 0; // nums[i] 到 nums[j]的子序和 for (let j = i; j < nums.length; j++) { thisSum += nums[j]; // 對於相同的i,不同的j,只要在j-1次循環的基礎上累加1項即可 if (thisSum > maxSum) {// 如果剛得到的這個子序和更大 maxSum = thisSum; // 則更新結果 } } }

return maxSum;

}; ```

可以看出,它的時間複雜度只有 $$O(N^{2})$$ 當然,這樣也是跑不了LeetCode

其實看到$$O(N^{2})$$,馬上反應的就是:把它降到 $$O(NlogN)$$ 怎麼做呢?

③ 分而治之

我們採用的算法思想就是——分而治之
1) 把它分成兩個或多個更小的問題;
2) 分別解決每個小問題;
3) 把各小問題的解答組合起來,即可得到原問題的解答。

放到這題,我們具體的做法就是:把這段數列先一分為二,然後在子數列裏再進行一分為二。將一個大問題化解成許多的小問題來處理,然後再分別跨域各自分界線,將問題組合起來。

image.png

我們來舉一個具體的例子吧,先給一個數列

image.png

以上將它對分對分(以取左邊為例)

image.png

image.png

最大子列和為4,其他類似,我們得到

image.png

再跨越中間分界線

image.png

左邊的最大子列和是6,右邊類似

image.png

最後再在中間求最大子列和得到結果

image.png

最大子列和為11

編碼實現如下

```js /* * @param {number[]} nums * @return {number} / function maxSubArray(nums) { let len = nums.length

if(len === 0){
    return 0
}

return maxSubArraySum(nums, 0, len - 1)

};

// 計算交叉的最大子序和 function maxCrossingSum(nums, left, mid, right){ let sum = 0 let leftSum = -Infinity for(let i = mid; i >= left; i--){ sum += nums[i] if(sum > leftSum){ leftSum = sum } }

sum = 0
let rightSum = -Infinity
for(let i = mid + 1; i <= right; i++){
    sum += nums[i]
    if(sum > rightSum){
        rightSum = sum
    }
}
return (leftSum + rightSum)

}

// 計算最大子序和函數【遞歸】 function maxSubArraySum(nums, left, right){

if(left === right){
    return nums[left]
}

let mid = Math.floor((left + right)/2)

let leftSum = maxSubArraySum(nums, left, mid)
let rightSum = maxSubArraySum(nums, mid+1, right)
let crossSum = maxCrossingSum(nums, left, mid, right)

return max3(leftSum, rightSum, crossSum)

}

// 返回3個數中的最大值 function max3(num1, num2, num3){ return Math.max(num1, Math.max(num2, num3)) } ```

終於能跑出來了,就是效率還是不行

image.png

④ 分治優化:線段樹

我們進行優化,分治還有一種方法 線段樹求解最長公共上升子序列問題 ,我們直接看代碼

```js function Status(lSum, rSum, mSum, iSum) { this.lSum = lSum; // lSum 表示 [l,r] 內以 l 為左端點的最大子段和 this.rSum = rSum; // rSum 表示 [l,r] 內以 r 為右端點的最大子段和 this.mSum = mSum; // mSum 表示 [l,r] 內的最大子段和 this.iSum = iSum; // iSum 表示 [l,r] 的區間和 }

function pushUp(lSub, rSub){

// iSum 就是 左子區間和 + 右子區間的和
const iSum = lSub.iSum + rSub.iSum;

// lSum 就是 左子區間的lSum 和 左區間
const lSum = Math.max(lSub.lSum, lSub.iSum + rSub.lSum);

// rSum 表示 [l,r] 內以 r 為右端點的最大子段和
const rSum = Math.max(rSub.rSum, rSub.iSum + lSub.rSum);

// mSum 表示 [l,r] 內的最大子段和
const mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);

return new Status(lSum, rSum, mSum, iSum);

}

// 查詢 a 序列 [l,r] 區間內的最大子段和 function getInfo(a, l, r){ // 遞歸終止條件 if (l === r) { return new Status(a[l], a[l], a[l], a[l]); }

// 下面是"分"的過程
// 得到中間值
const m = (l + r) >> 1;
// 分治:求左邊
const lSub = getInfo(a, l, m);
// 分治:求右邊
const rSub = getInfo(a, m + 1, r);

return pushUp(lSub, rSub);

}

var maxSubArray = function(nums) { return getInfo(nums, 0, nums.length - 1).mSum; }; ```

這裏的時間複雜度是$$O(N)$$ 空間複雜度 $$O(logN)$$

image.png

⑤ 在線處理

thisSum 維護一個 向右累加 子序和 如果之前和子序和都沒有第i個元素大,就從i開始重新維護一個 累加子序和

maxSum 保存遍歷過程中的最大子序和

```javascript /* * @param {number[]} nums * @return {number} / var maxSubArray = function(nums) { // 當前子序和 let thisSum = 0; // 最大子序和 let maxSum = nums[0];

// 遍歷一遍序列
for(let i = 0; i < nums.length; i++){

    if(thisSum + nums[i] < nums[i]){
        thisSum = nums[i];
    }else{
        thisSum += nums[i];
    }

    if(thisSum > maxSum){
        maxSum = thisSum;
    }
}

return maxSum;

}; ```

精簡一下代碼

```javascript /* * @param {number[]} nums * @return {number} / var maxSubArray = function(nums) { let thisSum = 0; let maxSum = nums[0];

for(let i = 0; i< nums.length; i++){
    thisSum = Math.max(thisSum + nums[i], nums[i]);
    maxSum = Math.max(maxSum, thisSum);
}

return maxSum;

}; ``` 這裏的時間複雜度是$$O(N)$$, 空間複雜度是$$O(1)$$

在這裏插入圖片描述

「其他文章」