问题描述
一个只包含正负数的数组，求出连续元素之和最大的子数组。
解决1：暴力求解方法
尝试每个元素的组合，最终选出合适的子数组，这种的时间复杂度为：O(n^2)，代码如下：
(defun find-maximum-subarray-1 (arr)
"暴力穷举"
(let ((len (length arr))
(start 0)
(end 0)
(max-sum (aref arr 0)))
(dotimes (i len (values start end max-sum))
(let ((tmp 0))
(do ((j i (1+ j)))
((>= j len))
(setf tmp (+ tmp (aref arr j)))
(if (> tmp max-sum)
(progn
(setf max-sum tmp)
(setf start i)
(setf end j))))))))
解决2：分治策略求解方法
如果有一个数组a[low ... high]，用分治策略求解子数组时，需要将a分解成两个规模相等的子数组，也就是说，找到相对父数组的中央位置，比如mid，然后考虑寻找两个子数组a[low ... mid]和a[mid + 1 ... high]最大子数组。假设此时已经无法分解子数组，设最大连续子数组为a[i ... j]，那么它的为止必定是下列三种情况之一：
- 1 完全位于a[low ... mid]中，(low <= i <= j <= mid)
- 2 完全位于a[mid + 1 ... high]中，(mid < i <= j <= high)
- 3 跨越中点，(low <= i <= mid < j <= high)
前两种情况可以通过分治策略递归的求解问题，第三种情况因为有必须跨越中点这个限制，所以也很容易线性时间内求解问题：
lisp版本：
(defun find-max-crossing-subarray (arr low mid high)
"
寻找跨越下标mid的最大子数组
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, higt)
left-sum = -∞
sum = 0
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, left-sum + right-sum)
"
(let ((left-sum (aref arr mid))
(right-sum (aref arr (+ mid 1)))
(max-left mid)
(max-right (+ mid 1))
(sum1 0)
(sum2 0))
(do ((i mid (1- i)))
((< i low))
(progn
(setf sum1 (+ sum1 (aref arr i)))
(if (> sum1 left-sum)
(progn
(setf left-sum sum1)
(setf max-left i)))))
(do ((j (+ mid 1) (1+ j)))
((> j high))
(progn
(setf sum2 (+ sum2 (aref arr j)))
(if (> sum2 right-sum)
(progn
(setf right-sum sum2)
(setf max-right j)))))
(values max-left max-right (+ left-sum right-sum))))
scala版本：
/**
* @param arr 数组
* @param low 数组左闭下标
* @param mid 中点
* @param high 数组右闭下标
* @return (左下标，右下标，元素最大之和)
*/
def `find-max-crossing-subarray`(arr: Array[Int], low: Int, mid: Int, high: Int): (Int, Int, Int) = {
var ls = arr(mid) //left sum
var rs = arr(mid + 1) //right sum
var ml = mid //max left index
var mr = mid + 1 //max right index
var sum1 = 0 //tmp sum for left
var sum2 = 0 //tmp sum for right
for (i <- mid to low by -1) {
sum1 = sum1 + arr(i)
ls = sum1 match {
case sum: Int if sum > ls => {
ml = i
sum
}
case _ => ls
}
}
for (i <- (mid + 1) to high) {
sum2 = sum2 + arr(i)
rs = sum2 match {
case sum: Int if sum > rs => {
mr = i
sum
}
case _ => rs
}
}
(ml, mr, ls + rs)
}
下面，就可以写出最大子数组的完整代码了：
(defun find-maximum-subarray (arr low high)
"
寻找最大子数组 分治算法
FIND-MAXIMUM-SUBARRAY(A, low, high)
if low == high
return (low, high, A[low]) //only one element
else
mid = floor((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 + 1, 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)
"
(if (= low high)
(values low high (aref arr low))
(let ((mid (floor (/ (+ low high) 2))))
(multiple-value-bind (left-low left-high left-sum) (find-maximum-subarray arr low mid)
(multiple-value-bind (right-low right-high right-sum) (find-maximum-subarray arr (+ mid 1) high)
(multiple-value-bind (cross-low cross-high cross-sum) (find-max-crossing-subarray arr low mid high)
(cond ((and (> left-sum right-sum) (> left-sum cross-sum)) (values left-low left-high left-sum))
((and (> right-sum left-sum) (> right-sum cross-sum)) (values right-low right-high right-sum))
(t (values cross-low cross-high cross-sum)))))))))
或者：
/**
* @param arr 数组
* @param low 数组左闭下标
* @param high 数组右闭下标
* @return (左下标，右下标，元素最大之和)
*/
def `find-maximum-subarray` (arr: Array[Int], low: Int, high: Int): (Int, Int, Int) = {
if (low == high)
return (low, high, arr(low))
else {
val mid = math.floor((low + high) / 2).toInt
val left = `find-maximum-subarray`(arr, low, mid)
val right = `find-maximum-subarray`(arr, mid + 1, high)
val cross = `find-max-crossing-subarray`(arr, low, mid, high)
if (left._3 >= right._3 && left._3 >= cross._3)
return (left._1, left._2, left._3)
else if (right._3 >= left._3 && right._3 >= cross._3)
return (right._1, right._2, right._3)
else
return (cross._1, cross._2, cross._3)
}
}
find-max-crossing-subarray时间复杂度为线性阶，根据递归树可以分析出find-maximum-subarray的时间复杂度为nlgn，所以分治策略求解最大子数组问题为O(nlgn)，比暴力求解有更改效率。
