53. Maximum Subarray

  1. 实际场景
  2. 分治策略求解
  3. 动态规划求解

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

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

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

实际场景

在实际生活中,通常会出现一个场景,炒股的人盯着一只股票涨跌情况在分析这只股票一段时间内,何时买进买出才能达到收益的最大化。通常人们想到的是“低价买进,高价卖出”,这是最理想的情况,但是实际情况中,你可能无法做到。比如下图中股票 A,最高价格出现在第 0 天,而最低价格出现在第 3 天,显然无法做到低买高卖。于是你可能会想也许满足其中的任意一个条件,得到的结果就是最优结果。不否认,股票 A 如果在第 3 天最低价的时候买进,确实能达到收益最大化。但是股票 B 给出了一个反例,最大收益既不是在最低价格时买进,也不是在最高价格时卖出。

天数 1 2 3 4
差值 -30 20 -50 30

分治策略求解

分治策略,最常见的实际应用就是归并排序。说到分治策略,就是递归地求解一个问题。在每层递归中分三个步骤解决问题:

  • 分解(Devide),将问题划分为相同的子问题;
  • 解决(Conquer),求解子问题,如果达到条件直接求解,未达到条件则继续递归;
  • 合并(Combine),将子问题的解合成原问题的解。
    递归的计算方式有通用公式:T(n) = aT(n/b) + f(n)。
    最大子数组每次都是最数组进行二等分,所以公式为:T(n) = 2T(n/2) + f(n),那么时间复杂度就是 O(nlgn)。
    我们要通过分治策略来寻找数组 A[low..high] 的最大子数组,意味着我们要将子数组划分为两个规模相等的子数组。首先找到子数组的中央位置 mid,然后考虑求解两个子数组 A[low..mid] 和 A[mid+1..high]。我们很容易发现最大子数组 A[i..j] 所处的位置必然是以下情况之一:
  • 完全位于子数组 A[low..mid] 中,那么 low ≤ i ≤ j ≤ mid
  • 完全位于子数组 A[mid+1..high] 中,那么 mid < i ≤ j ≤ high
  • 子数组跨越了中点,那么 low ≤ i ≤ mid < j ≤ high
    算法核心示意图
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.maxSubSum(nums, 0, len(nums) - 1)

    def maxSubSum(self, subArray, left, right):
        if left == right :
            return subArray[left]

        mid = (left + right) // 2
        maxLeftSum = -sys.maxsize - 1
        maxRightSum = -sys.maxsize - 1
        maxMidSum = -sys.maxsize - 1
        maxLeftSum = self.maxSubSum(subArray, left, mid)
        maxRightSum = self.maxSubSum(subArray, mid + 1, right)
        maxMidSum = self.maxCrossingSubSum(subArray, left, mid, right)
        return max(maxLeftSum, maxRightSum, maxMidSum)

    def maxCrossingSubSum(self, subArray, left, mid, right):
        sum = 0
        maxLeftSum = -sys.maxsize - 1
        maxRightSum = -sys.maxsize - 1
        for i in range(mid,left-1,-1) :
            sum += subArray[i]
            maxLeftSum = max(sum, maxLeftSum)
        sum = 0
        for i in range(mid+1, right+1) :
            sum += subArray[i]
            maxRightSum = max(sum, maxRightSum)
        return maxLeftSum + maxRightSum

动态规划求解

动态规划(dynamic programming)与分治策略相似,这里的 programming 指的是一种表格法,都是通过组合子问题的解来求解原问题。分治法将问题划分为互不相交的子问题,递归的求解子问题,再将他们的解组合起来,求出原问题的解。与之相反,动态规划应用于 子问题重叠 的情况,即不同的子问题具有公共的子子问题。在这种情况下,分治策略会做许多不必要的工作,它会反复的求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了这种不必要的工作。

动态规划方法通常用来求解 最优化问题,这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解,而不是最优解,因为可能有多个解都达到最优值。

通常按照 4 个步骤来设计动态规划算法:

  • 寻找一个最优解的结构特征。
  • 递归的定义最优解的值。
  • 计算最优解的值,通常采用自底向上的方法。
  • 利用计算出的信息构造一个最优解。

最大子数组里面,我们首先要想清楚一个问题就是对于 maxSubArray(A, i) 来说,如果它是目前最大的数组,那么子数组 maxSubArray(A, i - 1) 一定是非负数,因为 maxSubArray(A, i - 1) > maxSubArray(A, i - 1) + A[i],所以不难得出一个结论:maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) + A[i] : A[i];

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        # state
        maxSum = - sys.maxsize - 1
        for num in nums :
            sum = max(num, sum + num)
            maxSum = max(maxSum, sum)
        return maxSum
  1. leetcode record

请多多指教。

文章标题:53. Maximum Subarray

本文作者:顺强

发布时间:2020-04-22, 23:59:00

原始链接:http://shunqiang.ml/leetcode-53-maximum-subarray/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏