-
Notifications
You must be signed in to change notification settings - Fork 1
/
maxsub.go
44 lines (39 loc) · 980 Bytes
/
maxsub.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
package maxsub
import (
"math"
"github.com/catorpilor/leetcode/utils"
)
func maxSubSum(nums []int) int {
return twoPasses(nums)
}
// twoPasses time complexity O(N), space complexity O(1)
func twoPasses(nums []int) int {
n := len(nums)
first := useKadane(nums, n)
preSum := 0
for i := range nums {
preSum += nums[i]
nums[i] = -nums[i]
}
preSum += useKadane(nums, n)
if first > 0 {
return utils.Max(first, preSum)
}
return first
}
// useKadane use kadanes's algorightms to find the max sum subarray
// but dit some modification, since we want non-empty subarray.
func useKadane(nums []int, n int) int {
var maxEndingHere int
maxSofar := math.MinInt32
for i := 0; i < n; i++ {
maxEndingHere += nums[i]
if maxEndingHere > maxSofar {
maxSofar = maxEndingHere
}
if maxEndingHere < 0 {
maxEndingHere = 0
}
}
return maxSofar
}