LESSON 208 OF 348 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in Kotlin: O(n²) Brute Force with Running Sums

Practice O(n²) Read the full explanation

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^2) time and use O(1) extra space.

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1.

for each i : 0 -> n - 1:
		for each j : i -> n - 1:

We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case:

maxSum = nums[0]
for each i : 0 -> n - 1:
	for each j : i -> n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum

All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array which gives extra space of O(n). There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]).

maxSum = nums[0]
for each i : 0 -> n - 1:
	for each j : i -> n - 1:
		maxSum = max(maxSum, sum)
return maxSum

How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0:

maxSum = nums[0]
for each i : 0 -> n - 1:
	sum = 0
	for each j : i -> n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7

Guided

Ctrl + Enter to check

Maximum Sum Subarray in Kotlin, explained

Problem overview

The function maxSumSubarray receives an IntArray named nums that may hold positive and negative numbers. It returns the largest sum that a continuous subarray of nums can have: a run of neighbouring elements, from some start index to some end index, with no gaps.

For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7. The subarray [6, -2, -3, 1, 5] adds up to 7, and no other run of neighbours does better. The statement sets a budget of O(n²) time and O(1) extra space, so trying every subarray is acceptable here, as long as it doesn't use an extra array.

Approach: try every start and every end

A subarray is fixed by two indices: the first one, i, and the last one, j, with 0 <= i <= j < n. There are about n²/2 such pairs, so checking them all fits the budget, provided each sum is available in constant time.

Adding up nums[i..j] from scratch for every pair would cost an extra loop and push the total to O(n³). Prefix sums would fix that, but they need an extra array, which breaks the O(1) space limit. The cheaper trick is to fix i and let j grow one step at a time. Moving from j - 1 to j adds exactly one element, nums[j], so one running variable, sum, holds the current subarray's total. When i moves on, the running sum starts again from 0.

On the example, with i = 2 the running sum takes the values 6, 4, 1, 2, 7, 1 as j goes from 2 to 7. The best of those, 7, beats everything seen for the earlier starts, and no later start does better.

Other lessons on the same problem improve on this approach, so the quadratic version here is the baseline. It is the simplest correct solution, and it is the one to write first.

Step by step

Declare maxSum as nums[0]. Not 0: every subarray sum can be negative, and the answer must be the sum of a real subarray. The single-element subarray nums[0] is a valid starting candidate.
Loop over the start index i with nums.indices, which is the range 0 to nums.size - 1.
Declare sum as 0 inside that loop. It is declared there because each start needs a fresh, empty running sum, and nothing outside the loop uses it.
Loop over the end index j from i up to the last index, using i until nums.size. Starting at i means the first subarray tried has a single element.
Add nums[j] to sum. Now sum is the total of nums[i..j].
Update maxSum in one line with maxOf(maxSum, sum), which returns the larger of its two arguments.
Return maxSum once both loops are done.

The solution in Kotlin

class Solution {

    fun maxSumSubarray(nums: IntArray): Int {
        var maxSum = nums[0]
        for (i in nums.indices) {
            var sum = 0
            for (j in i until nums.size) {
                sum += nums[j]
                maxSum = maxOf(maxSum, sum)
            }
        }
        return maxSum
    }
}

The Kotlin details worth knowing:

Ranges. i until nums.size excludes its upper bound, so j stops at nums.size - 1. i..nums.size - 1 means the same thing. Writing i..nums.size would be a bug: the last index it produces is out of bounds.
nums.indices. It is the range 0..nums.size - 1. It avoids the off-by-one that comes from writing the bound by hand.
maxOf. It is a standard-library function that returns the larger of two values, and it works for Int as well as other comparable types.
var inside the loop. sum is created again on each pass of the outer loop, so it starts at 0 every time. It's a var because += reassigns it.
Int overflow. Int is a 32-bit type, and arithmetic that goes beyond its range wraps silently without any error. For [2000000000, 2000000000], the two-element sum doesn't fit and wraps to -294967296, so the function returns 2000000000. The lesson's inputs stay in range; with larger values, use Long for sum and maxSum.

Complexity

Time: O(n²). For each start i, the inner loop runs n - i times, so the total number of steps is n + (n - 1) + ... + 1, which is n(n + 1)/2. Each step does constant work: one addition and one comparison.

Space: O(1). The function uses maxSum, sum, i and j, regardless of the size of the input.

Edge cases and common mistakes

All negative numbers. [-4, -2, -9] gives -2, the best single element. Starting maxSum at 0 would wrongly return 0, a sum that no non-empty subarray has.
A single element. [7] gives 7.
All positive numbers. [1, 2, 3] gives 6, the whole array.
Forgetting to reset sum. If sum is declared before the outer loop, each start continues from the previous total, so the result is no longer a subarray sum.
Starting j at 0 or i + 1. With 0, the code adds elements before i. With i + 1, it skips the one-element subarray nums[i], which is wrong for [-10, 5]: the answer is the single 5, but the function would return -5.
An empty array. nums[0] throws an ArrayIndexOutOfBoundsException. The code assumes at least one element.

Testing

[-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
[-4, -2, -9] gives -2.
[7] gives 7.
[1, 2, 3] gives 6.
[-10, 5] gives 5.

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

Start learning free