[ LeetCode  ]

LeetCode 53: Maximum Subarray

最大子序和问题是 DP 算法的一个很经典的问题。(也可使用分治算法。)

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

样例:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解法

很明显这是一个求最优的问题,所以想到用 DP 来做。实施 DP 之前要先确定子问题的形式,之后才能通过这个形式来获得一个原始问题的子问题的递推关系,然后通过自底向上的方法实现。

最开始想到的子问题的形式可能是 maxSubArray(int A[], int i, int j),即 A[i:j] 的最大子序和。但这个形式很难找到原始问题怎么和子问题联系起来:你如何对原始问题进行划分?

另一个思路是,考虑以某个元素结尾的子序列的最大子序和问题,即 maxSubArray(int A[], int i)。这样原始问题就是 maxSubArray(A, A.length),而问题和子问题的递推公式容易得到:

maxSubArray(A, i) = A[i] + maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0

有了递推公式,实现 DP 就很容易了。

实现

这个实现使用了一个“表格” dp,是为了更符合 DP 算法的常规处理方式。去掉处理边界情况的代码,主要逻辑其实只有 for 循环那两行。

class Solution:
    def maxSubArray(self, nums):
        if nums == []:
            return None
        
        dp = [nums[0]] * len(nums)  # 初始化表格
        for i in range(1, len(nums)):
            dp[i] = nums[i] + (dp[i - 1] if dp[i - 1] > 0 else 0)
            
        return max(dp)

由于每个问题仅仅依赖前一个子问题,故从子问题图1可以得到时间复杂度为 $O(N)$;由于使用了 dp 数组,所以空间复杂度也为 $O(N)$。

观察到我们每次计算只是用到 dp[i]dp[i-1],所以仅用两个变量 curprev 来替代整个数组也能完成算法:

class Solution:
    def maxSubArray(self, nums):
        if nums == []:
            return None
        
        maximum = cur = prev = nums[0]
        for i in range(1, len(nums)):
            cur = nums[i] + (prev if prev > 0 else 0)
            maximum = max(maximum, cur)
            prev = cur
            
        return maximum

此时空间复杂度降低为 $O(1)​$。

参考

(本文完)

  1. 子问题图是一个有向图,每个顶点唯一地对应一个子问题,其中的边代表子问题之间的依赖关系。通常,一个子问题的求解时间与子问题图中对应顶点的(出射边的数目)成正比,而子问题的数目等于子问题图的顶点数。因此,通常情况下,DP 算法的运行时间与子问题图中边的数量成正比。——《算法导论》第15章:动态规划