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

bindong · · 1243 次点击 · · 开始浏览

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

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

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