pythontip 100days-day14

Code › python
, ,

题目

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

例子

  • [-2,1,-3,4,-1,2,1,-5,4] -> 6

假设

  • 输入的数组元素为整数

tips

  1. 枚举所有子数组，检查每个子数组和
  2. 你能想到更优的解法吗？(利用动态规划思想)

答案

解法1:

def maxSubArray(nums):
    max_ = nums[0]
    for i in range(len(nums)):
        for j in range(i + 1,len(nums) + 1):
            sub_sum = sum(nums[i:j])
            if sub_sum > max_:
                max_ = sub_sum
    return max_

性能

  1. 时间复杂度O(n^3)
  2. 空间复杂度O(1)

关键点

  1. 枚举所有子数组并计算和

解法2:

def maxSubArray(nums):
    tmp = nums[0]
    max_ = tmp
    n = len(nums)
    for i in range(1,n):
        # 当当前序列加上此时的元素的值大于tmp的值，说明最大序列和可能出现在后续序列中，记录此时的最大值
        if tmp + nums[i]>nums[i]:
            max_ = max(max_, tmp+nums[i])
            tmp = tmp + nums[i]
        else:
        #当tmp(当前和)小于下一个元素时，当前最长序列到此为止。以该元素为起点继续找最大子序列,
        # 并记录此时的最大值
            max_ = max(max_, tmp, tmp+nums[i], nums[i])
            tmp = nums[i]
    return max_

性能

  1. 时间复杂度O(n)
  2. 空间复杂度O(1)

关键点

  1. 动态规划