53. Maximum Subarray

Leetcode 問題: 53. Maximum Subarray
Categories:
Tags:

題目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

傳入一 數字陣列 nums，陣列中的數字 有正數有負數，找出子序列中，加總最多的序列

e.g. 序列 [-2,1,-3,4,-1,2,1,-5,4]

整數序列 nums -2 1 -3 4 -1 2 1 -5 4
最大加總序列 4 -1 2 1

加總答案是 4 - 1 + 2 + 1 = 6

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23

演算法

1. 選擇起始點，當作目前加總最多的數字

有數字的話一定要回傳加總數字，如果陣列都是負數的話，也要想辦法找出負數最小的數是哪一個

所以所有負數都是單獨計算，直到有找到 加總起來是正數，就會以那個正數當起點計算

  • 正數不管再怎麼選也比負數大

EX1. 整數序列 [-1]

整數序列 nums -1
最大加總序列 -1

加總答案是 - 1

EX2. 整數序列 [-3, -1]

整數序列 nums -3 -1
最大加總序列 -1

加總答案是 - 1

EX3. 整數序列 [-3, -1, 1]

整數序列 nums -3 -1 1
最大加總序列 1

加總答案是 1

2. 當遇到第一個正整數，表示至少整體加總的最大數字一定是正整數（只選一個）

當遇到第一個正整數，會將加總最多的序列設定為目前數字，且確定加總數字一定會是正數，至少是自己本身一個正數

所以當後方的數字，與前面的數字做加總，只要小於 0就一定不是要找的序列，因為加總後，後面的負數會完全抵消前面的正數，所以要重新計算新的序列

EX1. 整數序列 [-1, 3, -1, 1, -4]

整數序列 nums -1 3 -1 1 -4
最大加總序列 3

正數 3 後面的加總，無法超過 3 本身 甚至會變成負的 3 - 1 + 1 -4 = -1

當加總 小於 0 表示這一整個序列中間都是做白工，完全沒辦法讓原本序列變大，所以當發現這樣的序列，導致加總會變成 負數，那就可以直接跳過不用檢查，除非這個序列的加總可以超過 原本正數 3 本身

EX2. 整數序列 [-1, 3, -1, 1, 2]

整數序列 nums -1 3 -1 1 -4
最大加總序列 3 -1 1 2

最大加總序列為 3 - 1 + 1 + 2 = 5，雖然中間有負數，但也有正數可以相互抵銷影響，直到加總的數字超過 原本正數 3 本身

那加總最大序列就會從 [3] 變成 [3, -1, 1, 2]，最大加總數字會從 3 變成 5

所以要能夠讓 加總最多的序列 能夠大於目前數字的條件有

  • 後方連接 正數 與 加總最多的序列（目前數字） 再加總，變成更大的 加總最多的序列
  • 後方連接 負數，但後方也有其他的正數可以抵消這個負數的影響，直到後方的正數加總起來超過原本的加總最多的序列（目前數字），就可以找到最新的加總最多的序列

3. 紀錄當前加總最多的總和

當 沒有新的加總數字 超過 先前加總數字，原本的最大加總數字不變

當 有新的加總數字 超過 先前加總數字，取最大的數字當作 新的加總數字

直到最後的那個最大加總數字，就是能夠找出的加總最多的序列總和

答案

JavaScript

/**
 * @param {number[]} numsList
 * @return {number}
 */
var maxSubArray = function(numsList) {
    // 最大子序列加總大小，預設是第 1 個數字
    // - 避免傳入的數字只有 1 個負數，然後加總也沒辦法變成正數，所以預先設定加總是第 1 個
    // - e.g. [-1]
    let maxSubSum = numsList[0];
    // 計算後方加總數字
    let currentSum = 0;

    for (let i = 0; i < numsList.length; i++) {
        // 目前數字
        let currentNumber = numsList[i];
        if (currentSum < 0) {
            // 假如後方加總數字，沒辦法整體維持正數的話，表示加上這個數字沒有任何幫助，直接重來砍掉重練
            currentSum = 0;
        }
        // 「目前加總數字」加上「目前數字」
        currentSum += currentNumber;
        // 取得目前加總數字最大的那個
        // - 如果「目前加總的數字」大於「之前最大加總數字」，表示「目前的子序列」可以取代「之前的子序列」
        // - 如果「目前加總的數字」小於或等於「之前最大加總數字」，表示「目前的子序列」要再加油，還沒贏過之前的序列
        maxSubSum = Math.max(maxSubSum, currentSum);
    }

    return maxSubSum;
};

參考資料