53.md

题目地址

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

解答1

class Solution:
    def maxSubArray(self, nums: list) -> int:
        """
            最大子序和

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

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

            r[0]代表代表全局最优解
            r[1]以当前位置为结尾的局部最优解

            for i in range(1, len(nums)):
                nums[i] = max(nums[i], nums[i] + nums[i-1])
            return max(nums)
        """
        from functools import reduce
        return reduce(lambda r, x: (max(r[0], r[1] + x), max(r[1] + x, x)), nums, (max(nums), 0))[0]

解答2

class Solution:
    def maxSubArrayHelper(self, nums, l, r):
        if l > r:
            return -2147483647
        m = (l + r) // 2

        leftMax = sumNum = 0
        for i in range(m - 1, l - 1, -1):
            sumNum += nums[i]
            leftMax = max(leftMax, sumNum)

        rightMax = sumNum = 0
        for i in range(m + 1, r + 1):
            sumNum += nums[i]
            rightMax = max(rightMax, sumNum)

        leftAns = self.maxSubArrayHelper(nums, l, m - 1)
        rightAns = self.maxSubArrayHelper(nums, m + 1, r)

        return max(leftMax + nums[m] + rightMax, max(leftAns, rightAns))

    def maxSubArray(self, nums):
        """
            最大子序和（分治法）

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

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

            r[0]代表代表全局最优解
            r[1]以当前位置为结尾的局部最优解

            for i in range(1, len(nums)):
                nums[i] = max(nums[i], nums[i] + nums[i-1])
            return max(nums)
        """
        return self.maxSubArrayHelper(nums, 0, len(nums) - 1)