LeetCode＃53. Maximum subarray sum

subject ：

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .

Example 2：

Input ：nums = [1]
Output ：1

Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

This problem is still a dynamic programming problem , We can get before n The sum of the elements , Then calculate once , Finally get the maximum value .

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