Kotlin Coding Test Course, Finding the Sum of Consecutive Numbers

Problem Description

Given an integer array arr, this is a problem of finding the maximum sum of a contiguous subarray.
In other words, you need to determine what the largest sum is when adding up a few consecutive numbers from arr.
This problem is one of the frequently asked coding test questions and can be solved using Kadane’s algorithm.

Problem Example

Input

[2, -1, 3, 4, -2, 1, -5, 4]

Output

10

Explanation: The sum of the contiguous subarray [3, 4, -2, 1] is the maximum at 10.

Approach to the Problem

Since this problem requires finding the sum of a contiguous subarray, the key is how to set the range.
That is, while you can approach this by fixing starting and ending points and summing all elements in between,
this method is inefficient. Instead, you can solve it in O(n) time complexity using Kadane’s algorithm.

Kadane’s Algorithm

Kadane’s algorithm works by updating the maximum sum of the contiguous subarray so far by comparing it to the current position’s value.
The specific steps are as follows:

  1. Initialize the variables maxSoFar and maxEndingHere. Both can be initialized to 0 or the first element of the array.
  2. Traverse the array and add the current value arr[i] to maxEndingHere.
  3. If maxEndingHere is greater than maxSoFar, update maxSoFar.
  4. If maxEndingHere becomes less than 0, reset it to 0 to start a new contiguous sum.

This method can find the maximum sum in O(n) time, regardless of the array size.

Kotlin Code Implementation

Below is the code that implements the above algorithm in Kotlin: 


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

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

    return maxSoFar
}

fun main() {
    val arr = intArrayOf(2, -1, 3, 4, -2, 1, -5, 4)
    val result = maxSubArraySum(arr)
    println("Maximum contiguous sum: $result")
}

The above code defines a function maxSubArraySum that calculates the maximum contiguous sum from a given integer array.

Time Complexity Analysis

Since Kadane’s algorithm derives results through a single traversal of the array, its time complexity is O(n).
Therefore, increasing the size of the array does not significantly affect performance. The space complexity is O(1) and is very efficient as it does not use any additional data structures.

Conclusion

The problem of finding contiguous sums is a frequently encountered issue in algorithm problem solving,
and can be efficiently solved through Kadane’s algorithm. This allows you to learn the basics of Kotlin syntax and algorithm design at the same time.
Since this is a problem that often appears in coding tests, practice it to be able to implement it naturally.

Additional Practice Problems

Try additional practice with the following modified problems:

  • Write a program that outputs both the starting and ending indices of the contiguous subarray from the given array.
  • Find the maximum contiguous sum when given an array with all negative elements.
  • Create a program that receives multiple test cases and outputs the maximum contiguous sum for each.

References