实际场景

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

股票情况

解题思路

我们想找到收益最大化的方法，其实可以换一个角度来看数据。我们是想寻找一段日期，在日期范围内股票价格的净变化值最大，所以可以考察每日价格变化的差价，第 i 天的价格差价为第 i 天和第 i-1 天的价格差，如下表所示，那么把这个看成数组，问题就转化成寻找数组的 和最大的非空连续子数组。我们称这样的连续子数组为 最大子数组（maximum subarray）。

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

虽然做了变换，但是对于 n 天的日期，通过暴力求解的方式，所需要的时间复杂度仍然为 O(n²)。

解题方法

暴力求解

刚刚讲过，通过暴力求解的方式，并不能降低时间复杂度。算法如下：

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var maxSum = Int.min
        for i in 0..<nums.count {
            var sum = 0
            for j in i..<nums.count {
                sum += nums[j]
                maxSum = max(sum, maxSum)
            }
        }
        return maxSum
    }
}

思路上面很简单，其实用枚举法把所有子数组的和全部算出来进行比较，然后选出其中最大的。在 LeetCode 53. Maximum Subarray 上提交，会出现 Submission Result: Time Limit Exceeded，显然时间复杂度太高。

Time Limit Exceeded

分治策略求解

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

分解（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 {

    func maxCrossingSubSum(_ subArray: [Int], _ left: Int, _ mid: Int, _ right: Int) -> Int {
        var sum = 0
        var maxLeftSum = Int.min
        var maxRightSum = Int.min

        for i in (left...mid).reversed() {
            sum += subArray[i]
            maxLeftSum = max(sum, maxLeftSum)
        }

        sum = 0

        for i in mid+1...right {
            sum += subArray[i]
            maxRightSum = max(sum, maxRightSum)
        }

        return maxLeftSum + maxRightSum
    }

    func maxSubSum(_ subArray: [Int], _ left: Int, _ right: Int) -> Int {
        if left == right {
            return subArray[left]
        }

        let mid = (left + right) / 2
        var maxLeftSum = Int.min
        var maxRightSum = Int.min
        var maxMidSum = Int.min

        maxLeftSum = maxSubSum(subArray, left, mid)
        maxRightSum = maxSubSum(subArray, mid + 1, right)
        maxMidSum = maxCrossingSubSum(subArray, left, mid, right)

        return max(maxLeftSum, maxRightSum, maxMidSum)

    }

    func maxSubArray(_ nums: [Int]) -> Int {

        return maxSubSum(nums, 0, nums.count - 1)
    }
}

动态规划求解

动态规划（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 {

    func maxSubArray(_ nums: [Int]) -> Int {

        var sum = 0
        var maxSum = Int.min
        for num in nums {
            sum = max(num, sum + num)
            maxSum = max(maxSum, sum)
        }

        return maxSum
    }
}

PS：动态规划这一部分稍后会详细的博客讲解。

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/09/21/MaximumSubArray/