-
Notifications
You must be signed in to change notification settings - Fork 1
/
maximum-subarray.go
53 lines (45 loc) · 978 Bytes
/
maximum-subarray.go
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
package algorithms
func maxSubArray(nums []int) int {
right := len(nums) - 1
left := 0
return findMaxSubArray(nums, left, right)
}
func findMaxSubArray(num []int, left int, right int) int {
if left == right {
return num[left]
} else {
mid := (right + left) / 2
leftMax := findMaxSubArray(num, left, mid)
rightMax := findMaxSubArray(num, mid+1, right)
crossMax := findCrossMaxSubArray(num, left, mid, right)
return max(leftMax, rightMax, crossMax)
}
}
func findCrossMaxSubArray(nums []int, left, mid, right int) int {
leftSum := nums[mid]
sum := nums[mid]
for i := mid - 1; i >= left; i-- {
sum += nums[i]
if sum > leftSum {
leftSum = sum
}
}
rightSum := nums[mid+1]
sum = nums[mid+1]
for i := mid + 2; i <= right; i++ {
sum += nums[i]
if sum > rightSum {
rightSum = sum
}
}
return leftSum + rightSum
}
func max(values ...int) int {
max := values[0]
for _, v := range values {
if v > max {
max = v
}
}
return max
}