[Question]: Find max sum in an given array
func findSubArrayWithMaxSumKadane(arr: inout [Int]) -> (sumValue: Int, startIndex: Int, endIndex: Int) {
var sum = 0
var maximumValue = 0
// variables to capture start and end index
var startIndex = 0
var endIndex = 0
var progressiveStartIndex = 0
//
for i in 0..<arr.count {
sum += arr[i]
if sum > maximumValue {
maximumValue = sum
startIndex = progressiveStartIndex
endIndex = i
}
if sum < 0 {
sum = 0
progressiveStartIndex = i+1
}
}
return (sumValue: maximumValue, startIndex: startIndex, endIndex: endIndex)
}
var kadaneArray = [-2,1,-3,4,-1,2,1,-5,4]
let kadaneSum = findSubArrayWithMaxSumKadane(arr: &kadaneArray)
print("The kadaneSum is:", kadaneSum)