53-maximum-subarray.md

53. Maximum Subarray - 最大子序和

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

示例:

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

进阶:

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

---

题目标签：Array / Divide and Conquer / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

这题Wrong Answer了很多次。

先求数组的累加和，然后在累加和数组最前面插个0。然后，问题就转化成了类似Best Time to Buy and Sell Stock。为什么说类似呢？因为，买卖股票的问题可以不发生交易，但本题，子数组不能为空。所以，当不发生交易时，就返回数组的最大值。

Language	Runtime	Memory
python3	52 ms	N/A

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 
        prices = list(itertools.accumulate(nums))
        prices.insert(0, 0)
        min_price = prices[0]
        dp = [0] * len(prices)
        for i in range(1, len(prices)):
            dp[i] = max(dp[i-1], prices[i] - min_price)
            min_price = min(min_price, prices[i])
        if dp[-1] == 0:
            return max(nums)
        else:
            return dp[-1]