53. Maximum Subarray

Leetcode

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

題目

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

解答

方法一 - 雙層迴圈暴力解

第一層迴圈代表起始的那個數字，第二層迴圈去找出在起始數字固定下，有可能的最大加總值是多少

var maxSubArray = function (nums) {
    let max = nums[0];

    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            max = Math.max(max, accu);
        }
    }

    return max;
};

結果：Time Limit Exceeded

參考資料

https://ithelp.ithome.com.tw/articles/10278815?sc=iThomeRithelp.ithome.com.tw

方法二 - Kadane's演算法

Kadane's演算法，有人認為是貪婪算法，也有人認為是 DP 動態規劃，根據這篇文章應該比較算是 DP

從動態規劃的方向思考：以陣列中的某個元素來看，到這個元素為止的子陣列，其加總的最大值會是多少呢？

核心公式是：

到某個元素為止的最大值 = "自己的值" 或是 "前一個元素的最大值 + 自己的值"

以下直接來看例子抓感覺

先以 [4, -1, -2, 1] 舉例：

第一個元素: 4

最大值為 4

子陣列為: [4]

第二個元素: -1

最大值為 "自己(-1)" or "前一個元素的最大值 (4) + 自己(-1)" = 3

子陣列為: [4, -1]

第三個元素: -2

最大值為 "自己(-2)" or "前一個元素的最大值 (3) + 自己(-2)" = 1

子陣列為: [4, -1, -2]

第四個元素: 1

最大值為 "自己(1)" or "前一個元素的最大值 (1) + 自己(1)" = 2

子陣列為: [4, -1, -2, 1]

=> 最後解答要的最大值為第二個元素時的 3

接著再以 [-2, 1, -3, 4, -1] 舉例來看：

第一個元素: -2

最大值為 -2

子陣列為: [-2]

第二個元素: 1

最大值為 "自己(1)" or "前一個元素的最大值 (-2) + 自己(1)" = 1

子陣列為: [1]

第三個元素: -3

最大值為 "自己(-3)" or "前一個元素的最大值 (1) + 自己(-3)" = -2

子陣列為: [1, -3]

第四個元素: 4

最大值為 "自己(4)" or "前一個元素的最大值 (-2) + 自己(4)" = 4

子陣列為: [4]

第五個元素: -1

最大值為 "自己(-1)" or "前一個元素的最大值 (4) + 自己(-1)" = 3

子陣列為: [4, -1]

=> 最後解答要的最大值為第四個元素時的 4

觀察以上範例後，會發現核心公式只有兩條：

到某個元素為止的最大值 = "自己的值" 或是 "前一個元素的最大值 + 自己的值"
於每一輪中紀錄子陣列加總最大值 = "原本的子陣列加總最大值" + "到某個元素為止的最大值"

var maxSubArray = function (nums) {
    // 最大總和數
    let max = nums[0];
    // 到某個元素為止的最大值
    let sum = nums[0];

    for(let i=1; i<nums.length; i++) {
        sum = Math.max(nums[i], sum + nums[i]);
        max = Math.max(max, sum);
    }

    return max;
};