Go算法——最大子数组问题
2020-02-12 本文已影响0人
ProgrammingGuy
package main
import (
"fmt"
"math"
)
func findMaxCrossingSubarray(array []int, l, m, h int) (lb, hb, _ int) {
sum := 0
lsum, rsum := math.MinInt64, math.MinInt64
for i := m; i >= l; i-- {
sum += array[i]
if sum > lsum {
lsum = sum
lb = i
}
}
sum = 0
for i := m + 1; i <= h; i++ {
sum += array[i]
if sum > rsum {
rsum = sum
hb = i
}
}
return lb, hb, lsum + rsum
}
func findMaxSubarray(array []int, l, h int) (_, _, _ int) {
if l == h {
return l, h, array[l]
}
m := (l + h) / 2
ll, lh, lsum := findMaxSubarray(array, l, m)
hl, hh, hsum := findMaxSubarray(array, m+1, h)
cl, ch, csum := findMaxCrossingSubarray(array, l, m, h)
if lsum >= hsum && lsum >= csum {
return ll, lh, lsum
}
if hsum >= lsum && hsum >= csum {
return hl, hh, hsum
}
return cl, ch, csum
}
func main() {
arr := []int{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}
fmt.Println(arr)
fmt.Println(findMaxSubarray(arr, 0, len(arr)-1))
}