Q53-最大子序和-简单-动态规划

53. 最大子序和

本题和Q16是一样的

Question

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

Example 1:

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

Example 2：

输入：nums = [1] 输出：1

Note:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

进阶：如果你已经实现复杂度为 的解法，尝试使用更为精妙的 分治法 求解。

Approach 1: 动态规划

老规矩，动态规划问题第一步思考两个问题

• 表示什么；
• 状态方程怎么更新；

这里假设表示以 i 个元素结尾的子数组的最大和；更新方式为： 表示继续沿用上一次的子数组并更新为第 i 处的子数组最大和。表示另起一个新组数组作为第 i 处的子数组最大和。

def maxSubArray(self, nums) -> int:
    n = len(nums)
    dp = [0]*n
    dp[0] = nums[0]
    for i in range(1,n):
        dp[i] = max(dp[i-1] + nums[i], nums[i])
    return max(dp)

复杂度分析

• 时间复杂度 O(N)： 线性遍历数组 nums
• 空间复杂度 O(N)： 需要建立dp

Approach 2: 滚动数组

建立一个长度为n的dp数组的确比较浪费空间，我们可以牺牲时间复杂度来换取空间复杂度。建立变量dp和sumA，sumA存储前 i 个元素组成的子数组最大值，每一步都和新的dp比较大小并更新。

def maxSubArray1(self, nums) -> int:
    sumA = dp = nums[0]
    for i in range(1,len(nums)):
        dp = max(dp + nums[i], nums[i])
        sumA = max(sumA, dp)
    return sumA

复杂度分析

• 时间复杂度 O(N)： 线性遍历数组 nums
• 空间复杂度 O(1)： 需要建立常数个变量

方法1中需要建立一个长度为n的dp数组，使得空间复杂度为，实际上可以使用一个滚动数组的概念把空间复杂度降低到。即把dp[0 : i-1]中最大的值赋值给一个变量，每次迭代都更新它，最后用这个变量输出结果。

def maxSubArray1(self, nums) -> int:
    dp = 0
    maxA = nums[0]
    for i in range(len(nums)):
        dp = max( nums[i], dp + nums[i])
        maxA = max( dp, maxA )
    return maxA

复杂度分析

• 时间复杂度 O(N)： 线性遍历数组 nums
• 空间复杂度 O(1)： 需要建立常数个变量