最大子数组

Posted on

Maximum subarray

算法形式

例如对于不对变化的股票，要怎么买入买出才能是效益最大化，将问题从寻找数据的最大值最小值变成考察数据相对于前一个点的变化大小，这样问题就变为了寻找最大的非空连续子数组，即最大子数组
依旧采取分治策略来求解，假设我们要寻找子数组A[low..high]的最大子数组，根据分治思想将该数组分为两个规模相等的子数组，设切分点为mid，则最大子数组必然出现在以下三种情况中

  • 完全位于A[low..mid]中
  • 完全位于A[mid..high]中
  • 介于中间

递归求解前两种情况的子问题和母问题相同，问题在于介于中间这种情况，假设该数组为A[i..mid..j]，因为必须过mid这个点，所以分别向左和向右寻找最大子数组，然后合并即可，该过程可以在线性时间内完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
left-sum=0
sum=0
for i = mid downto low
	sum = sum+A[i]
	if sum > left-sum
		left-sum=sum
		max-left=i
right-sum=0
sum=0
for i = mid+1 upto high
	sum=sum+A[i]
	if sum>right-sum
		right-sum=sum
		max-right=j
return(max-left,max-right,left-sum+right-sum)

第一个for循环找左半部的最大子数组，第二个for循环在找右半部的最大子数组，最后返回最大子数组的边界和最大子数组的值

1
2
3
4
5
6
7
8
9
10
11
12
FIND-MAXIMUM-SUBARRAY(A,low,high)
if high==low
	return(low,high,A[low])
else mid=(low+high)/2
	(left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low，mid)
	(right-low,right-high,right-sum)=FIND-MAXIMUM-SUBARRAY(A,mid，high)
	(cross-low,cross-high,cross-sum)=FIND-MAX-CROSSING-SUBARRAY(A,low，mid,high)
if left-sum>=right-sum and left-sum>=cross-sum
	return(left-low,left-high,left-sum)
elseif right-sum>=left-sum and right-sum>=cross-sum
	return(right-low,right-high,right-sum)
else return(cross-low,cross-high,cross-sum)

7-12行为合并工作，因为第七行求子数组并非原问题的子问题，所以看作是合并部分

算法分析

$n=1$时，$T(1)=\Theta(1)$
$n>1$时，求解子问题需要$2T(n/2)$的时间，而求解cross问题则需要$\Theta(n)$时间，因此总的递归式为$T(n)=2T(n/2)+\Theta(n)$,根据主方法求解得$T(n)=\Theta(nlgn)$

源代码

习题解答

Ex4.1-3

指出规模为$n_0$是暴利算法和递归算法的性能交叉点

算法改进

最大子数组其实存在一个线性时间的算法，但不是使用分治策略