Kadane’s Algorithm: Max subarray sum in an array

[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)

Leave a Comment

Your email address will not be published. Required fields are marked *