【第十七天 - 动态规划 题目分析】

• 先简单回顾一下，今天预计分析的题目： 53. Maximum Subarray

• 题目叙述：https://leetcode.com/problems/maximum-subarray/

• 题目叙述：

  • 题目会给一个 nums 的 list，需要找出至少一个数字的连续值，他们相加的结果会是最大的
    

• 测资的 Input/Output

  • 会给一个 nums 的 list，需要回传连续相加最大的值
    

• 这种题目「暴力的解法」就是把每个相加的值储存起来，找出最大的值 (max)
  

• 若有N笔资料，那暴力解法的

  • 时间成本：需要两个回圈，大约 O(N^2)
  • 空间成本：需要 N*N 的空间

• 由於他是要算最佳解，我们只要记录 max 即可

  • 我们从第2个位置( index = 1 )开始读取 nums
    • 若前一个位置大於 0 (才有累加的价值)，就将此位置+前一个位置的值
    • 若前一个位置小於等於 0 (没有必要累加)，就不用理他，此位置就保持原状
      

• python 实作

    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            for i in range (1, len(nums)):
                if(nums[i-1] > 0):
                    nums[i] = nums[i]+nums[i-1]
                    
            return max(nums)