Maximum Subarray Sum in Kotlin | Kadane’s Algorithm

by

Kadane’s Algorithm is a dynamic programming algorithm used to find the maximum subarray sum in an array of numbers. The subarray can be any contiguous subset of the given array. It was developed by computer scientist Jay Kadane in 1984.

The algorithm works by iterating through the array and keeping track of the maximum sum found so far and the maximum sum ending at the current index. At each index, the maximum sum ending at that index is either the current element or the sum of the current element and the maximum sum ending at the previous index. The maximum sum found so far is updated if the maximum sum ending at the current index is greater than the current maximum.

Kotlin
fun kadane(arr: IntArray): Int {
    var maxSoFar = arr[0]
    var maxEndingHere = arr[0]

    for (i in 1 until arr.size) {
        maxEndingHere = maxOf(arr[i], maxEndingHere + arr[i])
        maxSoFar = maxOf(maxSoFar, maxEndingHere)
    }

    return maxSoFar
}

This function takes an integer array arr as input and returns the maximum subarray sum. It works by iterating through the array and keeping track of the maximum sum found so far and the maximum sum ending at the current index. At each index, the maximum sum ending at that index is either the current element or the sum of the current element and the maximum sum ending at the previous index. The maximum sum found so far is updated if the maximum sum ending at the current index is greater than the current maximum.

Kotlin
fun kadane(arr: IntArray): Int {
    var maxSoFar = arr[0]
    var maxEndingHere = arr[0]

    for (i in 1 until arr.size) {
        maxEndingHere = maxOf(arr[i], maxEndingHere + arr[i])
        maxSoFar = maxOf(maxSoFar, maxEndingHere)
    }

    return maxSoFar
}
fun main(){
    val arr = intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)
	val maxSubArraySum = kadane(arr)
	println(maxSubArraySum) 			// Output: 6

}

In this example, the input array arr is [-2, 1, -3, 4, -1, 2, 1, -5, 4], and the output is 6, which is the maximum subarray sum.

That is 4-1+2+1 = 6

Leave a Comment