* 给定N个正数列{A1, A2, A3,......,AN}, 求连续片段的最大值 ~~~ package main import ( "fmt" "math/rand" "time" ) //TODO : 时间复杂度 T(N) = O(N^3) func MaxSum1(number []int) (max int) { t := time.Now() max = 0 for i := 0; i < len(number)-1; i++ { for j := i; j <= len(number)-1; j++ { sum := 0 for k := i; k <= j; k++ { sum += number[k] } if sum > max { max = sum } } } fmt.Println("Values:", max, "TODO1:", time.Since(t), ) return max } //TODO : 时间复杂度 T(N) = O(N^2) func MaxSum2(number []int) (max int) { t := time.Now() max = 0 for i := 0; i < len(number)-1; i++ { sum := 0 for j := i; j <= len(number)-1; j++ { sum += number[j] if sum > max { max = sum } } } fmt.Println("Values:", max, "TODO2:", time.Since(t), ) return max } //TODO : 时间复杂度 T(N) = O(N) func MaxSum3(number []int) (max int) { t := time.Now() sum := 0 max = 0 for i := 0; i <= len(number)-1; i++ { sum += number[i] if sum > max { max = sum } if sum < 0 { sum = 0 } } fmt.Println("Values:", max, "TODO3:", time.Since(t), ) return max } func main() { //TODO : 生成数据 rand.Seed(time.Now().Unix()) number := make([]int, 3000, 1000000) for k, _ := range number { number[k] = rand.Intn(50) - 25 } //TODO : 1 MaxSum1(number) //TODO : 2 MaxSum2(number) //TODO : 3 MaxSum3(number) } ~~~