NASA666

不以物喜,不以己悲.
Posted on , viewed 568 times

求连续子数组的最大和

问题是这样的:一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2},最大连续子数组的和为5+2-1+2=8。

在每次元素累加和小于0时,从下一个元素重新开始累加。实现代码如下:
package main
import (
    "fmt"
)
func main() {
    arr := [...]int{2, 4, -7, 5, 2, -1, 2, -4, 3}
    l, r, sum := 0, -1, 0
    max := -9999
    for index, num := range arr {
        sum += num
        if sum <= 0{
            sum = 0
            l = index + 1
        }
        if sum > max{
            r = index
            max = sum
        }
    }
    fmt.Println(max)
    fmt.Println(l)
    fmt.Println(r)
}