剑指 Offer 42. 连续子数组的最大和(动态规划/贪心)

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

示例1:

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

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

动态规划解法

这道题的动态规划说实话没想到。。。。

状态定义：设动态规划列表dp，dp[i]代表以元素nums[i]为结尾的连续子数组最大和。

转移方程：若dp[i-1]<=0，那么dp[i-1]对dp[i]产生的是负贡献，即

当 dp[i - 1] > 0 时：执行 dp[i] = dp[i-1] + nums[i]；
当 dp[i−1]≤0 时：执行 dp[i] = nums[i] ；

初始状态dp[i] = nums[0]

返回值，dp数组中的最大值。

时间复杂度O(N)

空间复杂度O(1)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sumvalue= float('-inf')
        for i in range(1, len(nums)):
            nums[i] += max(nums[i-1], 0)
        return max(nums)

贪心解法

自己脑海里首先能想到的是贪心的做法：

初始maxvlaue=负无穷，sumvalue=负无穷，从前往后遍历数组

假如sumvalue <0，则更新sumvalue=num[i]，(此时说明从num[i]开始重新记录)

假如sumvalue >0，则更新sumvalue += num[i]

更新maxvalue

/*
 * 贪心法 O(n)
 *
 * 当叠加的和小于0时，就从下一个数重新开始，
 * 同时更新最大和的值(最大值可能为其中某个值)，
 * 当叠加和大于0时，将下一个数值加入和中，
 * 同时更新最大和的值，依此继续。
 *
 * 举例： nums = [-2,1,-3,4,-1,2,1,-5,4]
 * sum = INT_MIN <= 0-> sum = -2 <= 0 -> sum = 1 > 0 ->
 * -> sum = -2 <= 0 -> sum = 4 > 0 -> sum = 3 > 0 ->
 * -> sum = 5 > 0 -> sum = 6 > 0 -> sum = 1 > 0 ->
 * -> sum = 5 > 0
 * res = [-2, 1, 1, 4, 4, 5, 6, 6, 6]
 * 最终返回 res = 6
 * */

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxvalue = float('-inf')
        sumvalue = float('-inf')
        for i in range(len(nums)):
            if sumvalue <= 0:
                sumvalue = nums[i]
            else:
                sumvalue += nums[i]
            maxvalue = max(maxvalue, sumvalue)
        return maxvalue

时间复杂度O(N)

空间复杂度O(1)