LeetCode 刷題題目：53. Maximum Subarray

Jason Tseng

5 min readApr 9, 2024

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

題目如下：
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.

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

中文大意是從陣列之中找到一段陣列，這段陣列的加總比任何其他陣列的加總要來得大，最大的加總為何？

這題是一題在陣列的任意區間，找到最大的加總值，最暴力直觀的就是遞迴，也最好理解，解題思路大概是這樣

每一個都會生出兩個子 Function，最後剩一個的時候回傳當下那個值然後與前一個相加

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (!nums || nums.length == 0) {
        return 0
    }
    if (nums.length == 1) {
        return nums[0]
    }
    let sum = 0
    let nums1 = []
    let nums2 = []
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]
        if (i !== 0) {
            nums1.push(nums[i])
        }
        if (i !== nums.length - 1) {
            nums2.push(nums[i])
        }
    }
    sum = Math.max(sum, maxSubArray(nums1))
    sum = Math.max(sum, maxSubArray(nums2))
    return sum
};

因為遞迴是 O(2^N) 明顯會 Timeout

遞迴鐵定是會在效能上掛點，又因為是找區間問題，直接使用動態規劃了，透過迴圈來找出各項的最大和，所有組合都跑過一遍來互相比較留下最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (!nums || nums.length == 0) {
        return 0
    }
    if (nums.length == 1) {
        return nums[0]
    }
    let i = 1
    let max = nums[0]
    while (i < nums.length) {
        let sum = 0
        for (let j = i; j >= 0; j--) {
            sum += nums[j]
            max = Math.max(max, sum)
        }
        i++
    }
    return max
};

testcases 從 197 提升至204，掛點，畢竟 Nested Loop 還是 O(N²)

重新再看一次自己的圖，發現有重複的地方可以省略

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = nums[0]
    for (let i = 1; i < nums.length; i++) {
        nums[i] = Math.max(0, nums[i - 1]) + nums[i]
        if (nums[i] > max) {
            max = nums[i]
        }
    }
    return max
};

O(n) 解決

LeetCode 刷題題目：53. Maximum Subarray

Written by Jason Tseng