leetcode53-- Maximum Subarray

leetcode53-- Maximum Subarray

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

这个题是用DP来做的,即”maximum”为以nums[i]结尾的最大的值

maximum= max(maximum+nums[i], nums[i]) 要看它有没有包括当前的这个元素,

所以是

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        maximum = nums[0]
        res = nums[0]
        
        for i in range(1, len(nums)):
            maximum = max(maximum+nums[i], nums[i])
            res = max(res, maximum)
            
        return res

其中res是最后要返回的结果,要不断地更新,它们都初始化为数组的第一个数值,所以后面应该从第2相元素开始遍历.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦