[LeetCode 解題紀錄] 53. Maximum Subarray

53. Maximum Subarray

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

Problem:

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

Notes: A subarray is a contiguous non-empty sequence of elements within an array.

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

題意

這題題目簡單明瞭，希望從給定的一個整數陣列 nums，找出其中連續子陣列的最大和，並回傳這個最大和。

問題解析

首先要先確定一下「子陣列」的定義，這裡的子陣列代表的是「連續」、「非空值」的陣列。接著，解讀一下題目，這裡要求要回傳子陣列最大的「和」，我們也可以得到在解題的時候，只需要紀錄最大的和，並不需要真的把整個子陣列的內容給記錄下來。

解法

暴力解

假如一開始沒有想到最好的做法，首先，我們可以先用窮舉的方式，來整理一下解題的思路。

• 窮舉所有可能的子陣列。
• 計算每個子陣列的和。
• 比較所有子陣列的和，找出最大值。

function maxSubArray(nums) {
    let maxSum = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            let sum = 0;
            for (let k = i; k <= j; k++) {
                sum += nums[k];
            }
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

• 時間複雜度：O(n³)：三層迴圈，時間複雜度較高。
• 空間複雜度：O(1)：除了用於計算的變數，額外空間消耗較少。

減少重複計算 — Dynamic Programming 動態規劃

看一下剛剛的暴力法，我們可以思考一下，由於是一個連續的陣列，我們是不是並不需要每次都重新去計算每一個子陣列的總和呢？這時候我們就可以用上動態規劃的概念了，將計算過的值存起來，透過查表的方式來減少重複的計算。

Dynamic programming 概念複習：

演算法筆記系列 — Dynamic programming 動態規劃

• 狀態定義：dp[i] 表示以 nums[i] 結尾的子陣列的最大和。
• 狀態轉移方程：dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
• 初始狀態：dp[0] = nums[0]
• 返回值：dp 陣列中的最大值

function maxSubArray(nums) {
    const dp = new Array(nums.length);
    dp[0] = nums[0];
    let maxSum = dp[0];
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

• 時間複雜度：O(n)：只遍歷一次陣列。
• 空間複雜度：O(n)：需要額外的 dp 陣列。

優化空間複雜度 — Kadane’s Algorithm

Kadane’s Algorithm 可以理解成，解題思路類似動態規劃，但不需要額外的 dp 陣列，使用 curSum 與 maxSum 來記錄當下的變化。

Kadane’s Algorithm：

Maximum subarray problem - Wikipedia

• curSum：當前子數量的和。
• maxSum：到目前為止的最大子數列的和。
• 每回合更新當下子數列和，並且更新最大值。

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

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

    return maxSum;
};

• 時間複雜度：O(n)：只遍歷一次陣列。
• 空間複雜度：O(1)：不需要額外的空間。

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記