go语言实现寻找最大子数组

  1 /*
  2 寻找最大子数组go语言实现
  3 */
  4 
  5 package main
  6 
  7 import fmt "fmt"
  8 
  9 func main() {
 10     /*
 11     需要查找的数组
 12     */
 13     A:=[]int{-1,5,-3,-1,3,1,3}
 14     low:=0
 15     high:=len(A)-1
 16     sum:=0
 17     low,high,sum=find_max_array(A,0,len(A)-1)
 18     /*
 19     返回数组边界
 20     */
 21     fmt.Println(low," ",high," ",sum)
 22 }
 23 /*
 24 返回越过中间点的最大数组
 25 */
 26 func Find_max_acrossing(Array []int,low int,mid int,high int)(int,int,int) {
 27     /*
 28     现设定左最小值，寻找左边最小数组边界
 29     */
 30     left_sum:=-1000
 31     sum:=0
 32     max_left:=mid
 33     for i := mid; i>=low; i-- {
 34         sum+=Array[i]
 35         if sum>left_sum {
 36             left_sum=sum
 37             max_left=i
 38         }
 39     }
 40 
 41     /*
 42     现设定右最小值，寻找右边最小数组边界
 43     */
 44     right_sum:=-1000
 45     sum=0
 46     max_right:=mid+1
 47     for i := mid+1; i <=high; i++ {
 48         sum+=Array[i]
 49         if sum>right_sum {
 50             right_sum=sum
 51             max_right=i
 52         }
 53     }
 54     return max_left,max_right,left_sum+right_sum
 55 }
 56 
 57 func find_max_array(Array []int,low int,high int)(int,int,int){
 58     max_left:=low
 59     max_right:=high
 60     sum:=0
 61     if low==high {
 62         max_left=low
 63         max_right=high
 64         sum=Array[high]
 65     }else{
 66         mid:=0
 67         if (high-low+1)%2==0 {
 68             mid=(high+low-1)/2
 69         }else{
 70             mid=(high+low)/2
 71         }
 72 
 73         max_left_low:=low
 74         max_left_high:=mid
 75         left_sum:=0
 76         max_left_low,max_left_high,left_sum=find_max_array(Array,low,mid)
 77 
 78         max_right_low:=mid+1
 79         max_right_high:=high
 80         right_sum:=0
 81         max_right_low,max_right_high,right_sum=find_max_array(Array,mid+1,high)
 82 
 83         max_across_low:=low
 84         max_across_high:=high
 85         across_sum:=0
 86         max_across_low,max_across_high,across_sum=Find_max_acrossing(Array,low,mid,high)
 87 
 88         if left_sum>right_sum && left_sum>across_sum{
 89             max_left=max_left_low
 90             max_right=max_left_high
 91             sum=left_sum
 92         }else if right_sum>left_sum && right_sum>across_sum {
 93             max_left=max_right_low
 94             max_right=max_right_high
 95             sum=right_sum
 96         }else if across_sum>left_sum && across_sum>right_sum {
 97             max_left=max_across_low
 98             max_right=max_across_high
 99             sum=across_sum
100         }
101     }
102     return max_left,max_right,sum
103 }