LESSON 209 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray in Kotlin: Kadane's Algorithm in O(n)

( Kadane's Algorithm )

Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Maximum Sum Subarray in Kotlin, explained

Problem overview

Given an IntArray named nums that can hold positive and negative integers, maxSumSubarray returns the largest sum of any non-empty continuous run of elements. For [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the run [6, -2, -3, 1, 5].

Approach

The brute force tries every start and end and adds up each run, which is O(n^2) with a running sum or O(n^3) without one. The lesson wants O(n) time and O(1) extra space.

Kadane's algorithm looks at the question from the right edge. Let maxSum be the best sum of a subarray that ends at the current element. That subarray is either just the current element, or the current element added to the best subarray ending at the previous element. We only extend the previous one if its sum helps, that is, if it is positive:

maxSum = value + max(previous maxSum, 0)

The answer is the biggest maxSum seen at any position, because the best subarray has to end somewhere.

Trace on the example, with maxSum starting at 0:

value	maxSum	result
-2	-2	-2
-5	-5	-2
6	6	6
-2	4	6
-3	1	6
1	2	6
5	7	7
-6	1	7

After the -5, the running sum is negative, so at 6 the algorithm starts fresh instead of dragging the negative prefix along.

Step by step

Create result as a var equal to nums[0]. This is the best sum found so far. Don't start it at 0: if every number is negative, the best subarray is a single negative element, and 0 would be a wrong answer because the empty subarray isn't allowed. nums[0] is a real subarray sum, so it is a safe start.
Create maxSum as a var equal to 0. It is the best sum of a subarray ending at the current position. Starting at 0 stands for "nothing before the first element".
Loop over the elements with for (value in nums). The name value is used because val is a keyword.
Update maxSum with value + maxOf(maxSum, 0). If the previous sum is positive, extend it; if it is zero or negative, drop it and start a new subarray at this element.
Update result with maxOf(result, maxSum).
Return result after the loop.

The solution in Kotlin

class Solution {
    fun maxSumSubarray(nums: IntArray): Int {
        var result = nums[0]
        var maxSum = 0
        for (value in nums) {
            maxSum = value + maxOf(maxSum, 0)
            result = maxOf(result, maxSum)
        }
        return result
    }
}

Kotlin details worth knowing:

for (value in nums) iterates over the elements directly, with no index. Both variables are var because they change in every iteration.
maxOf(a, b) returns the larger of two numbers. It replaces an if / else and keeps the recurrence on one line.
The function reads nums[0], so an empty array throws an ArrayIndexOutOfBoundsException. The problem implies at least one element.
Sums are Int, 32 bits, and overflow wraps silently. With inputs whose sum could pass about 2.1 billion, change the types to Long.

Complexity

Time: O(n). The array is read once, with constant work per element.
Space: O(1). Only result and maxSum are stored.

Edge cases and common mistakes

All negative numbers. For [-4, -2, -7] the answer is -2, the largest single element. Starting result at 0 would return 0.
A single element. The loop runs once, maxSum equals that element, and result stays the same. The answer is the element itself.
Mixing up the two variables. maxSum must end at the current element, so it can drop earlier values. result keeps the best over all positions and must never decrease.
Resetting to 0 instead of to the element. Writing maxSum = maxOf(maxSum + value, 0) allows an empty subarray and breaks the all-negative case.
All zeros. The answer is 0.

Testing

[-2, -5, 6, -2, -3, 1, 5, -6] returns 7.
[-4, -2, -7] returns -2.
[5] returns 5.
[1, 2, 3] returns 6.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free