---

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; }; ```

測試是對的

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

這裡面一共用到了三次迴圈，所以他的時間複雜度為 $$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) 把各小問題的解答組合起來，即可得到原問題的解答。

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

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

以上將它對分對分（以取左邊為例）

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

再跨越中間分界線

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

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

最大子列和為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)) } ```

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

④ 分治優化：線段樹

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

```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)$$

⑤ 線上處理

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)$$