使用 Go 解決 LeetCode 問題：53. Maximum Subarray

Algorithm
, , ,

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

  • Example:
1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
  • Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxSubArray(nums []int) int {
	max := -(1 << 63)
	temp := 0

	// 疊代陣列中的每一個元素
	for _, v := range nums {
		// 判斷累計值加上當前數字是否比當前數字小
		if temp+v < v {
			// 如果較小，將累計值改為當前數字
			temp = v
		} else {
			// 如果較大，進行累計
			temp += v
		}

		// 判斷累計值是否比最大值大
		if temp > max {
			// 如果較大，將最大值設置為累計值
			max = temp
		}
	}

	return max
}

Note

假設有以下參數：

1
nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

說明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
第 1 次迴圈：

temp 為 0，v 為 -2，max 為 overflows int。

temp 和 v 的總和 -2，沒有比 -2 大，故將 temp 進行累計。

累計值比最大值大，故將 max 設置為 -2。

----------------------------------------
<t>
<m>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 2 次迴圈：

temp 為 -2，v 為 1，max 為 -2。

temp 和 v 的總和 -1，小於 1，故將 temp 設置為 1。

累計值比最大值大，故將 max 設置為 1。

----------------------------------------
    <t>
    <m>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 3 次迴圈：

temp 為 1，v 為 -3，max 為 1。

temp 和 v 的總和 -2，大於 -3，故將 temp 進行累計。

累計值沒有比最大值大。

----------------------------------------
    <t--->
    <m>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 4 次迴圈：

temp 為 -2，v 為 4，max 為 1。

temp 和 v 的總和 2，小於 4，故將 temp 設置為 4。

累計值比最大值大，故將 max 設置為 4。

----------------------------------------
           <t>
           <m>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 5 次迴圈：

temp 為 4，v 為 -1，max 為 4。

temp 和 v 的總和 3，大於 -1，故將 temp 進行累計。

累計值沒有比最大值大。

----------------------------------------
           <t--->
           <m>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 6 次迴圈：

temp 為 3，v 為 2，max 為 4。

temp 和 v 的總和 5，大於 2 故將 temp 進行累計。

累計值比最大值大，故將 max 設置為 5。

----------------------------------------
           <t------>
           <m------>
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 7 次迴圈：

temp 為 5，v 為 1，max 為 5。

temp 和 v 的總和 6，大於 1 故將 temp 進行累計。

累計值比最大值大，故將 max 設置為 6。

----------------------------------------
           <t--------->
           <m--------->
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 8 次迴圈：

temp 為 6，v 為 -5，max 為 6。

temp 和 v 的總和 1，大於 -5，故將 temp 進行累計。

累計值沒有比最大值大。

----------------------------------------
           <t------------->
           <m--------->
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

第 9 次迴圈：

temp 為 1，v 為 4，max 為 6。

temp 和 v 的總和 5，大於 4 故將 temp 進行累計。

累計值沒有比最大值大。

----------------------------------------
           <t---------------->
           <m--------->
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
----------------------------------------

最終返回：6

Code