41. 最大子数组

楚天乐 510 0 条

动态规划大法。

第一步,建模,得出递推公式

有一个数组A[n], 对于A[i] (0<i<n)位置向前(0位置方向)最大和为C[i], 那么

C[i] = Max(C[i-1] + A[i], A[i])

终止条件

C[0] = A[0]

这样子我们就得到了对于任意一个位置 0 <= i < n,数组中从0到i的最大子串和。

但是我们的目标并不是求i位置,最大子串和。我们的目标是求整个数组上,最大子串和,也就是

Opt(A) = Max(C[i]), 0 <= i < n

第二步,试着实现算法

class Solution:
    def maxSubArray(self, nums):
        # write your code here
        length = len(nums)
        c = [0] * length
        c[0] = nums[0]
        maxSum = c[0]

        i = 1
        while i < length:
            if c[i-1] + nums[i] > nums[i]:
                c[i] = c[i-1] + nums[i]
            else:
                c[i] = nums[i]
            if c[i] > maxSum:
                maxSum = c[i]

            i += 1

        return maxSum

代码优化:

  1. 化简判断条件
  2. 我们求解C[i]只需要C[i-1], 所以我们并不需要存下所有的C[i]。我们只需要一个变量prev存储C[i-1]的值即可达到目的。
    所以代码可以经简称这样

    class Solution:
    def maxSubArray(self, nums):
        length = len(nums)
        maxSum = nums[0]
        prev = maxSum
    
        i = 1
        while i < length:
            if prev + nums[i] > nums[i]:
                prev = prev + nums[i]
            else:
                prev = nums[i]
    
            if prev > maxSum:
                maxSum = prev
    
            i += 1
    
        return maxSum

进一步优化,其实我们也不需要每次都用nums[i]去访问元素,因为这样可能会多一步寻址操作。我们改用for in

class Solution:
    def maxSubArray(self, nums):
        if len(nums) == 0:
            return None

        maxSum = nums.pop(0)    # 最大值为0号元素
        prev = maxSum           # 设置初始条件C[0] = A[0]

        for num in nums:
            # current = max(prev + num, num)
            current = prev + num    
            if current < num:
                current = num

            # update max sum
            if current > maxSum:
                maxSum = current

            prev = current

        return maxSum

算法复杂度O(n)



与本文相关的文章

发表我的评论
'
昵称 (必填)
邮箱 (必填)
网址