mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
36 lines
594 B
Go
36 lines
594 B
Go
package leetcode
|
|
|
|
import "math"
|
|
|
|
func maxSubarraySumCircular(A []int) int {
|
|
n, sum := len(A), 0
|
|
for _, v := range A {
|
|
sum += v
|
|
}
|
|
kad := kadane(A)
|
|
for i := 0; i < n; i++ {
|
|
A[i] = -A[i]
|
|
}
|
|
negativeMax := kadane(A)
|
|
if sum+negativeMax <= 0 {
|
|
return kad
|
|
}
|
|
return max(kad, sum+negativeMax)
|
|
}
|
|
|
|
func kadane(a []int) int {
|
|
n, MaxEndingHere, maxSoFar := len(a), a[0], math.MinInt32
|
|
for i := 1; i < n; i++ {
|
|
MaxEndingHere = max(a[i], MaxEndingHere+a[i])
|
|
maxSoFar = max(MaxEndingHere, maxSoFar)
|
|
}
|
|
return maxSoFar
|
|
}
|
|
|
|
func max(a int, b int) int {
|
|
if a > b {
|
|
return a
|
|
}
|
|
return b
|
|
}
|