0053. Maximum Subarray - chasel2361/leetcode GitHub Wiki

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

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

這個問題我也只想得到硬幹的從頭數，會長這樣

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        m = -10**10
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                total = sum([nums[n] for n in range(i, j + 1)])
                if total > m:
                    m = total
        return m

可是這個解法的時間複雜度相當高，應該是O(N^2)，所以來看看雨蕭大大的寫法

他介紹了一個概念：動態規劃

動態規劃演算法的核心在於記住已經解決過的子問題的解

動態規劃的精神是，把一個大問題拆分成許多相依的小問題，當解決所有小問題之後就能順勢解決大問題。
這個題目的主要問題是，找到陣列中總和最大的連續子陣列。

此時可以衍生出兩個子問題：

1. 怎麼找到子陣列的總和？
2. 各個子陣列如何比大小？

為了解決這兩個問題，可以定義兩個變數：

1. curr：當前選取之子陣列總和
2. res：目前為止最大子陣列總和

[1] 如果當前選取子陣列總和大於零，則擴充子陣列
[2] 如果當前選取子陣列總和不大於零，則更新子陣列 (總和不大於零就沒有擴充的意義了)
[3] 將當前子陣列總和與最大子陣列總和比較

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        res = cur = nums[0]
        for i in range(1, l):
            if cur > 0:
                cur += nums[i]  # [1]
            else:
                cur = nums[i]  # [2]
        
            if cur > res:
                res = cur
        return res

由於題目要求連續子陣列，所以能夠使用這樣的方式來不停更新子陣列，此法的時間複雜度可以大幅降低到O(N)，空間複雜度是O(2)

參考了其他人的寫法之後，發現另一個概念一樣，但較為精簡的寫法：
把各式子陣列存在陣列裡，最後再回傳其中的最大值。

這個寫法少了一個判斷，時間複雜度仍然是O(N)，但空間複雜度是O(N)，較原本的方法稍大。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = nums[i] + (dp[i - 1] if dp[i - 1] > 0 else 0)
            """上面這行相當於下方程式碼
            if dp[i - 1] > 0:
                dp[i] = nums[i] + dp[i - 1]
            else:
                dp[i] = nums[i]
            """
        return max(dp)