Fork me on GitHub

算法学习 - 最大子数组问题 [Maximum Subarray]

实际场景

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

股票情况

解题思路

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

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

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

解题方法

暴力求解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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。

图示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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/