[JavaScript] LeetCode 53. Maximum Subarray (貪婪+動態規劃解法)

題目概要

在 nums 整數陣列中找出總和最大的連續子陣列(最少要有一個元素),並返回最大值。

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

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

解題技巧

  • 可以使用貪婪演算法(Greedy algorithm)或動態規劃(Dynamic programming)來解。

程式碼

貪婪演算法

用 for 循環遍歷一個一個元素慢慢往下加,然後將總和跟當前最大值比較,將比較大的值存下來。一旦當前的數小於 0 的時候就將當前總和歸零,繼續找下一個子陣列。

PS. 注意 max 一定要預設為 -Infinity,因為總和會有負數,如果設為 0 會是錯的。

var maxSubArray = function(nums) {
    let max = -Infinity; // 當前最大子序列的總和
    let sum = 0; // 當前總和
    for(let i = 0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(max, sum);
        
        if (sum < 0) sum = 0;
    }
    
    return max;
};
image 7 [JavaScript] LeetCode 53. Maximum Subarray (貪婪+動態規劃解法)

動態規劃

我們可以從第一個元素開始慢慢找,看包含第一個元素加第二個元素及第二個元素本身的總和哪個大,就選哪個繼續往下做,比如有一陣列為 [-2,1,-3,4,-1,2,1,-5,4]

  1. [-2, 1][1] 相比 -2 + 1 = -1 < 1,所以 [1] 較大,直接跳過 -2,將 [1] 設為最大子序列起始繼續往下
  2. [1, -3][-3] 是 1 – 3 = -2 > -3,所以將 [1, -3] 繼續往下
  3. [1, -3, 4][4] 是 4 比較大,所以拋棄 [1, -3],以 [4] 為最大子序列起始再往下做
  4. [4, -1][-1] 相比 4 – 1 = 3 > -1,所以將 [4, -1] 繼續往下
  5. [4, -1, 2][2] 相比 4 – 1 + 2 = 5 > 2 所以將 [4, -1, 2] 繼續往下
  6. [4, -1, 2, 1][1] 相比 4 – 1 + 2 + 1 = 6 > 1 所以將 [4, -1, 2, 1] 繼續往下
  7. [4, -1, 2, 1, -5][-5] 相比 4 – 1 + 2 + 1 – 5 = 1 > -5 所以將 [4, -1, 2, 1, -5] 繼續往下
  8. [4, -1, 2, 1, -5, 4][4] 相比 4 – 1 + 2 + 1 – 5 + 4 = 5 > 4 ,全部元素比較結束。

在這段遍歷中,我們可以得知 [4, -1, 2, 1] 這段子序列的總和是最大的,為 6,所以答案為 6。

比較核心的公式為: Math.max(arr[i - 1] + nums[i], nums[i]);

這裡面的 arr[i] 代表包含第幾個元素的最大值。

var maxSubArray = function(nums) {
    let arr = [];
    arr[0] = nums[0]; // 子序列必須至少包含一個元素
    let max = arr[0];

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

    return max;
};

有點難用文字說明,還是看程式碼最快。

image 8 [JavaScript] LeetCode 53. Maximum Subarray (貪婪+動態規劃解法)
0 0 評分數
Article Rating
訂閱
通知
guest

0 Comments
在線反饋
查看所有評論