///Maximum Subarray. Divide & Conquer. Θ(nlgn)
func maximumSubarray(_ array: [Int]) throws -> (Int, Int, Int) {
return try _maximumSubarray(array, low: 0, high: array.count-1)
}
func _maximumSubarray(_ array: [Int], low:Int, high:Int) throws -> (Int, Int, Int) {
//low>=0 NOT low>0
guard low<=high, low>=0 else { throw TestError.argumentFault }
if low == high { return (low, high, array[low]) }
let mid = (low+high)/2
let pre = try _maximumSubarray(array, low: low, high: mid)
let post = try _maximumSubarray(array, low: mid+1, high: high)
let cross = try crossSubarray(array, low: low, mid: mid, high: high)
if pre.2>=post.2, pre.2>=cross.2 { return pre }
if post.2>=pre.2, post.2>=cross.2 { return post }
return cross
}
func crossSubarray(_ array:[Int], low:Int, mid:Int, high:Int) throws ->(Int, Int, Int) {
//low>=0 NOT low>0
guard low<=mid, mid<=high, low>=0 else { throw TestError.argumentFault }
var maxLeft = Int.min, maxRight = Int.min, sum = 0, left = 0, right = 0
for i in (low...mid).reversed() {
sum += array[i]
if sum > maxLeft {
maxLeft = sum
left = i
}
}
sum = 0
//Start from mid+1 NOT mid
for i in mid+1...high {
sum += array[i]
if sum > maxRight {
maxRight = sum
right = i
}
}
return (left, right, maxLeft+maxRight)
}
var s = try Int.randomArray(above: -10, under: 10)
try maximumSubarray(s)
Maximum Subarray. Divide & Conquer. Θ(nlgn)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
