【DP】53. Maximum Subarray

问题描述：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路：

简单的动态规划题目：

• 创建 dp[len(nums)]，其中 dp[i] 表示以 i 位置结尾的数的最大子段和；
• 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])；
• 最后，max(dp) 就是最终的答案。

时间复杂度为O(n)，空间复杂度也为O(n)。

Python3 实现：

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

补充：

最小子段和问题可以转化为最大字段和问题，只需要将列表中的元素全部取反，然后求最大字段和，再将结果取反即可。

改进——解题思路2：

可以不用列表，只需要两个变量，一个记录局部最大子段和，一个记录全局最大子段和。当局部最大子段和大于0时，就累积当前的数字；否则，就把当前的数字作为当前最大子段和。每次循环判断之后，还要更新最大子段和的值。这样时间复杂度仍为 O(n)，但空间复杂度将为 O(1)。

Python3 实现2：

# 动态规划
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = nums[0]  # 全局最大
        tem = 0  # 局部最大
        for i in range(len(nums)):
            if tem > 0:
                tem += nums[i]
            else:
                tem = nums[i]
            ret = max(ret, tem)
        return ret

a = [-2,1,-3,4,-1,2,1,-5,4]
b = Solution()
print(b.maxSubArray(a))  # 6 # [4,-1,2,1]