Go算法——最大子数组问题

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))
}