Skip to content

Instantly share code, notes, and snippets.

@digoreis
Created July 4, 2018 22:10
Show Gist options
  • Save digoreis/637b40394b119f6ea54bce1144a36d49 to your computer and use it in GitHub Desktop.
Save digoreis/637b40394b119f6ea54bce1144a36d49 to your computer and use it in GitHub Desktop.
Algorithm for Maximun Sum of a SubArray in Swift
import Cocoa
func kadaneSumMaxSubArray(_ values: [Int]) -> Int {
guard let firstValue = values.first else { return 0}
var current = firstValue
var global = firstValue
for value in values[1 ..< values.count] {
current = (current + value) < current ? 0 : current
current = max(current, (current + value))
global = max(global, current)
}
return global
}
kadaneSumMaxSubArray([1,2,-1,0]) //3
kadaneSumMaxSubArray([1,0,-1,0]) // 1
kadaneSumMaxSubArray([1,1,-1,2,5,16,-10]) // 23
kadaneSumMaxSubArray([1,2,-1,15]) // 15
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment