MaxSubarray最大子序和问题

回顾leetcode原来做过的题，看到了经典的最大子序和问题，收藏了一个好回答。 这个问题是这样的（https://leetcode.com/problems/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. 就是给一组整数，找到一组连续的子序列，让子序列的和最大，并且返回最大和。 比如说： 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 子序列[4,-1,2,1]有最大的和6.

原来是这样做的：

代码语言：javascript复制

class Solution(object):
    def maxSubArray(self, nums):
        flag = False
        for num in nums:
            if num > 0:
                flag = True
        if flag == True:
            s = 0
            m = 0
            for num in nums:
                s  = num
                if s > 0 :
                    if s > m:
                        m = s
                else:
                    s = 0
            return m 
        else:
            return max(nums)

运行时间28ms，在时间上可以超过100%的python答案，不过怎么看怎么罗里吧嗦，而且遍历了两遍。发现在讨论区有个很精简的回答：

代码语言：javascript复制

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

想法非常巧妙。

欢迎关注公众号～

生信编程日常

编程算法

0 人点赞