【LeetCode】（動态規劃）-----0053.最大子序和

描述

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

from functools import lru_cache

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        len_num = len(nums)
        ant = [0] * len_num

        @lru_cache(1000)
        def dynamic_programming(index):
            if index == 0:
                ant[index] = nums[0]
                return nums[0]
            ant[index] = max(dynamic_programming(index - 1) + nums[index], nums[index])
            return ant[index]

        dynamic_programming(len_num - 1)
        return max(ant)
           

運作時間：64ms；運作消耗：36.2MB

ant[i]表示到i為止的最大連續子序和

dp思路：假設目前位為i，将nums[i]和dp(i-1)+nums[i]比較，較大值存入ant[i]并傳回。

存在的問題：因為直接套了遞歸，是以雖然用lru_cache()記錄了每次遞歸的運作結果，但在資料量小的情況下優化不明顯甚至更慢了。用for循環+條件判斷速度會快很多。