剑指 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

        本题使用动态规划的思想,定义 f(i) 为以第 i 个数字结尾的子数组的最大和。那么答案就是:

剑指 Offer 42. 连续子数组的最大和

        首先 f(0) 肯定等于数组中的第一个数的值,然后往后递推。到第 i 个数字时,我们可以假设当前这个数字一定会存在于最大和的序列中,但是我们要判断是不是要加上前面 i-1 个数字,也就是说要考虑第 i 个数字单独成一段还是要加上 f(i-1) 组成一个新的序列。那么递推式就出来了:

剑指 Offer 42. 连续子数组的最大和

         每次递推到一个新的数字时,将最大结果保存下来,避免陷入局部最优。代码如下:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res,max_num=0,nums[0]
        for i in nums:
            res=max(res+i,i)
            max_num=max(max_num,res)
        return max_num
上一篇:欢乐的代码-2


下一篇:CF487 B. Strip