///Maximum Subarray. Θ(n)
func maximumSubarray(_ array: [Int]) -> (Int, Int, Int) {
var low = -1, high = -1, sum = Int.min
var currentLow = -1, currentHigh = -1, currentSum = Int.min
for i in 0..<array.count {
if currentSum < 0 {
currentSum = array[i]
currentLow = i
} else {
currentSum += array[i]
}
currentHigh = i
if currentSum > sum {
sum = currentSum
high = currentHigh
low = currentLow
}
}
return (low, high, sum)
}
var s = try Int.randomArray(above: -10, under: 10)
maximumSubarray(s)
Maximum Subarray. Θ(n)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 为什么要初始化int max = 1; int min = 1;不是0或者Integer.MAX_VALUE In...
- Maximum Subarray ExampleGiven the array [−2,2,−3,4,−1,2,1...
