思路

貪心法：設定最小標志result為float(‘-inf’),遍歷一次數組元素進行求和，如果當前元素大于result，則更新result的值，如果sum小于0，則重新置0進行計算，最后返回result

class Solution:def maxSubArray(self, nums: List[int]) -> int:n=len(nums)result=float('-inf')sum=0for i in range(n):sum+=nums[i]if sum>result:result=sum if sum<0:sum=0return result

動態規劃法:首先定義動態規劃數組dp=[float(‘-inf’)]*n，dp[i]表示以第i個元素結尾的最大連續子數組和，初始狀態dp[0]為nums[0],遞推的公式為當前最大的和要么是前一個元素+nums[i]，要么是從當前元素nums[i]
重新開始，選擇最大值進行更新，最后返回。

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