Last active
March 28, 2019 03:31
-
-
Save thieunguyencrystal/b5b8b05ac0ec7d9a183ae6d7c319ec55 to your computer and use it in GitHub Desktop.
Maximum sum such that no two elements are adjacent
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Maximum sum such that no two elements are adjacent */ | |
func solution(_ array: [Int]) -> Int? { | |
let count = array.count | |
guard count >= 0 else { return nil } | |
var inclusion = array[0] | |
var exclusion = 0 | |
var newExclusion = 0 | |
for i in (1..<count) { | |
newExclusion = inclusion > exclusion ? inclusion : exclusion | |
inclusion = exclusion + array[i] | |
exclusion = newExclusion | |
} | |
newExclusion = inclusion > newExclusion ? inclusion : newExclusion | |
return newExclusion | |
} | |
let input = [1,3,5,7,5] | |
let output = solution(input) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment