Maximum Subarray - Leetcode 圖解演算法

發表於 更新於 分類於

題目

Leetcode 題目連結：https://leetcode.com/problems/maximum-subarray/

simple

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

撰寫一段程式碼，可以接受一個整數的陣列，找出最大總和的 子陣列 ，並且回傳這個總和。

範例 1
輸入: nums = [-2,1,-6,2,1]
結果: 3
解釋: 可以從子陣列 [2, 1] 中可以得到最大的總和 3

解題需知

因爲這一題提到的是 subarray 子陣列，代表元素在陣列中必須要是相鄰的

Subarray

暴力破解法

  • 新增一個存放最大總和的變數 maxSum，用第一個元素的值(nums[0])作爲初始值
  • 依序把每個元素都加起來到 curSum（可以後面直接看圖解）
  • 每次加總後的值都跟最大總和比較一次
    • 如果新的總和大於最大總和，那就更新最大總和
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0] # 新增一個存放最大總和的變數 `maxSum`，用第一個元素的值(`nums[0]`)作爲初始值
            
        for i in range(len(nums)):
            curSum = 0
            
            for j in range(i, len(nums)):
                curSum += nums[j] #依序把每個元素都加起來到 `curSum`
                maxSum = max(maxSum, curSum) # 每次加總後的值都跟最大總和比較一次, 如果新的總和大於最大總和，那就更新最大總和
        return maxSum

圖解過程

i = 0

i = 1

i = 2

i = 3

i = 4

這個過程會需要 i 走過所有的元素，而每次的 i 也都會用 j 走過所有的元素，所以這個演算法的時間複雜度會是 O(N^2)

可以再更好嗎？

藉由 Kadane’s Algorithm 的技巧，可以讓演算法在 O(N) 的時間複雜度完成

simple

Kadane 算法掃描一次整個數列的所有數值，在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）from Wiki

解題重點

  • 從第一個元素開始加總整個陣列的所有數值，計算到當前 index 的元素的子陣列的最大總和 curSum
  • 在題目要求的最大總和的前提下，如果 curSum 變成負值，那再繼續加上去只會造成反效果，可以直接從 0 開始（如程式碼的 Line 7）
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = 0

        for n in nums:
            curSum = max(curSum, 0)
            curSum += n
            maxSum = max(maxSum, curSum)

        return maxSum

圖解過程

kadane algorithm

以上就是所有的內容，希望圖解演算法過程有幫助到你，感謝你的收看 🙂