53. 最大子序和 [easy]

https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

通过次数278,688 | 提交次数538,640

First Try

2020-07-16

只要加上当前数字后仍然大于0，当前数字就可以保存到进行下一个数字的比较，毕竟是增益。问题是负数的处理，尤其是全都是负数的情况。

至于说分治算法，算了算了，没时间看太多了。看题解说是线段树，听过好几遍了，还是没有精力去研究。

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 问题是负数的处理，尤其是全都是负数的情况
        maxrv = max(nums)
        reserve = 0  # 一个都没选，就是0 
        for n in nums:
            if reserve + n <= 0:
                reserve = 0 
                continue 
            reserve += n 
            maxrv = max(maxrv, reserve)
        return maxrv 

执行用时：28 ms, 在所有 Python 提交中击败了65.25%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了5.00%的用户

53. 最大子序和 [easy]​

First Try​

53. 最大子序和 [easy]

First Try