題目出處

53. Maximum Subarray

難度

Easy

題目分類

Array, Divide and Conquer, Dynamic Programming

個人範例程式碼 – 2022/4/28

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0

        current_max_with_this = [nums[0]]

        for i in range(1, len(nums)):
            current_max_with_this.append(max(current_max_with_this[i-1]+nums[i], nums[i]))

        return max(current_max_with_this)

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

建一個新的 array，記錄”包含自己”的當前最大用

當前最大 = max(當前數字, 當前數字+到前一個之前最大)

input handling

如果 input not nums (沒有數字)，return 0

Boundary conditions

for 控制範圍

個人範例程式碼 – 2022/2/24

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [] # dp = the biggest answer 'include me'
        for i in range(len(nums)):
            if i == 0:
                dp.append(nums[i])
            else:
                bigger = max(nums[i], nums[i]+dp[i-1])
                dp.append(bigger)

        return max(dp)

說明

這題我使用的是 DP 的解法，
我宣告一個 DP 來儲存「包含自己的」時最好的答案。

換句話說，我將題目拆解成到「包含每一個 index 的當下」 都是一個小題目，將題目的答案儲存進 dp 中。

注意是「包含自己」的最好答案，也就是說，我們只需要比較「自己」與「dp(n-1)+自己」誰比較大。
DP 裡面都是「一定要包含自己的最佳解」，而不是「全域的最佳解」。

所以假設原來的題目變成：
nums = [1,2,-1,4]
dp = [1,3,2,6]

2 就是因為一定要包含「-1」，我們只有「-1」跟「-1+’包含前一個’的最大」誰比較大。