Solution to the maximum subarray problem in linear time : Complete code in Java

In this blog we are going to discuss the problem of finding the maximum contiguous sum of elements in an array. Now, that was a mouthful ! Don’t worry, we will break this problem up step by step so that you will get a thorough understanding of the problem and the solution. This problem is also referred to as the Maximum subarray problem.

Our first approach to the solution will be the usage of brute force technique and then we will move on to solve the problem using Kadane’s algorithm. As we write the code in Java, we will keep improving the code so that we get a complete understanding of each line of code required to solve this problem.

What is the maximum contiguous sum in a subarray ?

We have an array of integers as input. The array can contain both positive and negative values. Let’s break the 4 important words in ‘Maximum contiguous sum in subarray‘ :

  1. Subarray means part of an array.
  2. Sum is the addition of the elements of an array.
  3. Contiguous means a sequence, no breaks. Hence, contiguous sum means the addition should be between a sequence of values one after the other without a break.
  4. Maximum contiguous sum is finding the maximum value after adding such a sequence of values.

Let’s look at a few examples to understand this better-

Examples of contiguous and non contiguous subarray
Example of contiguous and non-contiguous elements in array

Barring the last one, all the other examples show contiguous elements in an array. It can be only a single element anywhere in the array. It can be 2,3…n elements as long as there is no break in between. Since these are all part of the array, we refer to them as subarray. In the last example, the green blocks form a subarray but they are not contiguous and hence cannot be part of the solution. Having understood the concept of a contiguous subarray, we need to find the maximum sum contiguous subarray.

Examples of maximum sum contiguous subarray
Examples of maximum sum contiguous subarray, answers are on the right

We have understood the concept of a contiguous subarray, now let’s understand the concept of maximum sum in a contiguous subarray. First, take a look at examples 1,2,3 and 4, they are quite straight forward. Starting from the leftmost element, add the elements one by one without breaking the sequence and try to get a maximum value as shown on the right.

Let’s take a look at example number 5. At first glance, it might seem that the answer is 12. But it’s not ! Let’s start from the left, initially, the sum is 0. Adding 10,the first element in the array, gives us 10. Add the 2nd element, -5 to it, gives us 5. Now we add 12 to it, this gives us a total of 17 which is bigger than 12.

Example 6 is also straight forward. Here, it might seem that 10 + 20 = 30 which is bigger than 20, but note that 10 and 20 are not contiguous. Let’s move to the last example, number 7.

Let us approach example number 7 step wise –

  1. We start in a similar way.Initially, the sum is 0, adding 30, the first element in the array to the sum, gives us 30. The maximum value so far is 30.
  2. Add -40 to it and we get -10. We don’t change the maximum value as it is greater than -10.
  3. Add 20 to it, we get a 10 and we again don’t change the maximum value.
  4. If we were to add 40 to it, we get a 50. At this point, we have a new maximum value of 50. But wait a minute…
  5. If you consider only the 2 last elements which form a subarray and add their values, we get 60, which is bigger than 50. So, 60 is the right answer.
  6. Let’s revisit step 2 and 3. The result upto step 2 is -10. Adding the next element, 20, gives us 10. But when we add that current element,20,the outcome of the addition results in lower value than the current element,20. Let’s rephrase it, the current element has higher value as compared to adding it to previous sum. This means, we can reset the continuity or discard the previous sum. Remember this, it is an important condition to solve this problem.

I hope that makes sense. If the current element by itself has a bigger value than adding it to the previous sum, it means we can discard the previous sum since we are on a quest to find contiguous maximum sum. If we did not do this, the previous sums will act as a deterrent to our overall sum. With this, we also restart the continuity from this point onwards.

Using brute force to solve the problem

Let’s consider the following example

30-402040
Sample input to find maximum contiguous subarray using brute force

We need to find the maximum sum contiguous subarray. A subarray as we know can be just a single element or a sequence of ‘n’ elements. Let’s take a simple approach to solve this problem.

  1. We put a marker at 30, initialize the sum to 0 and –
    • Add 30 to the sum , resulting in 30.
    • Add -40 to current sum, resulting in a sum of -10.
    • Add 20 to current sum, resulting in a sum of 10.
    • Add 40 to resulting sum, resulting in a sum of 50.
    • At every step above, compare the sums to maintain a maximum value among them. At the end, what we have done is explored every possible contiguous subarray from the first element, 30 and found maximum value among them.
  2. Add a marker at -40, re-initialize the sum to 0, maintain the current maximum value from step 1 and –
    • Add -40 to the current sum, resulting in -40.
    • Add 20 to the current sum, resulting in -20.
    • Add 40 to the current sum, resulting in 20.
    • At each step, compare the sum with the current maximum value to find maximum among them. All possible contiguous subarrays starting from the second element, 40 have been explored.
  3. Add a marker at 20, initialize the sum to 0 and –
    • Add 20 to current sum, resulting in 20.
    • Add 40 to current sum, resulting in 60.
    • At each step, compare each sum with maximum and find maximum among them. All the contiguous subarrays starting from 20 have been explored.
  4. Add a marker at 40, initialize the sum to 0 and:
    • Add 40 to current sum, resulting in 40,
    • In this step, compare the sum,40, with maximum obtained in steps above and set appropriate value.
    • This is the end of the array,we should have found maximum value by now.

Why are we putting markers ? We are putting these markers to have a kind of starting point for the subarray. A subarray can start at every element in the array. For an array of size 4, we put 4 markers. So, I hope you can imagine a ‘for’ loop from 0 – n representing each marker.

What do we do for each marker ? From the element being pinned (Sorry, too much usage of Zoom) as a marker, we first initialize sum to 0. Then we start adding the numbers after that pinned element upto the last element. So, another for loop inside the already existing loop, we get a nested for loop. Inside the nested for loop, we find the sum. So, sum = sum + element. Remember, we need to find the maximum at each step now. This can be done using another variable which will be compared against sum.

Brute force approach

As you can see above, the marker starts at the leftmost element and keeps moving ahead one by one. For each position of the marker, we iterate from the marker upto the end of the array and keep finding the sum. At every iteration ,we evaluate if we have found a new maximum value.

Code using brute force approach
public class MaxSumSubArray {

    public static void main(String[] args) {
        
        int[] arr = {30, -40, 20, 40};

        int sum = findMaxSum(arr);
        System.out.println("The maximum contiguous sum in the sub array is : " + sum);
    }

    private static int findMaxSum(int[] arr) {

        int currentSum;
        int maxSum = 0;

        for (int marker = 0; marker < arr.length; marker++) {
            //reinitialize sum when marker moves ahead.
            currentSum = 0;

            for (int j = marker; j < arr.length; j++) {
                currentSum = currentSum + arr[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }
}

Notice that on line 20, j is initialized to marker which moves ahead by one each time. We don’t want to find subarrays every time from the first element.

Does the code work for all inputs ?

The input that we passed has a mix of positive and negative numbers. What if we pass the input as a set of all negative numbers ? If we were to pass the input as {-30, -40 , -20 , -40} , we get the output as 0. We need to fix our code to handle this scenario. Take a look at the following code snippet –

private static int findMaxSum(int[] arr) {

    ...
    int maxSum = 0;

    for (int marker = 0; marker < arr.length; marker++) {
        ...
        for (int j = marker; j < arr.length; j++) {
            currentSum = currentSum + arr[j];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

As you can see, the maximum sum is initialized to 0. Since all the values in the array are negative values, the current sum is always a negative value, it is never greater than the maximum sum, which is 0. Hence the ‘if’ condition is never satisfied and the maximum sum is returned as 0.

The fix for this is changing a single line of code –

int maxSum = Integer.MIN_VALUE;

With this change, an input consisting of only negative values should work as expected.

Time complexity of the brute force approach

In the code above, there are 2 nested ‘for’ loops. For every position of the marker, we are iterating through the rest of the array. The time complexity of this code is hence O(N2). If you are completely new to the Big O notation, I would recommend this excellent article by Rob Bell.

The solution works and it is a decent way to get started. Once we have a working solution, we should start thinking along the lines of improving the code and the performance of the code. But remember, don’t get obsessed about improving the performance of every piece of code you write !

We can definitely do better in solving this problem by improving the time complexity to O(n). Let’s explore Kadane’s algorithm.

How to pronounce Kadane ?

Before we get started, I would like to sidestep a little bit with respect to the pronunciation of Kadane. We have a cricketer who goes by the name Ajinkya Rahane. His surname, Rahane , is pronounced as Ra-ha-‘nee’ with an emphasis on the ‘ne’. Kadane is not pronounced like that. It’s more like pronouncing the ‘cane’ in sugarcane or the way you pronounce ‘Dane’ when you refer to someone from Denmark. Peter Schmeichel is the most capped Danish footballer of all time, and the first Dane to reach 125 caps. There is no drag on the ‘ne’ in Dane. Similarly, don’t drag on the ‘ne’ in Kadane. By the way, his full name is Joseph Born Kadane, you can read more about him here. Hey Arsenal fans, speaking of Danes, you can’t forget the great Nicklas Bendtner, can you ? Let’s get back to Kadane’s algorithm now.

Kadane’s algorithm

You can get a good overview of the algorithm here. What is important to note is that, at any given index, the algorithm computes the subarray with the largest sum upto that index. Let’s get into an example.

30-402040
Example for Kadane’s algorithm

This is the same example which we considered when we used the brute force approach. When we went through the process step by step using brute force, do you remember a condition which was going to play a crucial role in solving this problem ?

If the current element by itself has a bigger value than adding it to the previous sum, it means we can discard the previous sum since we are in a quest to find maximum contiguous sum. If we did not do this, the previous sums will act as a deterrent to our overall sum.

Reset the sum since we found a better point for finding max sum continuity

The sum obtained up to the 2nd element is -10. Now, the next element is 20. If we add the previous sum of – 10 to 20, we get 10. However the current element, 20, is bigger than the sum. Why should we carry a baggage of lesser value as compared to the current element which is much bigger ? So, we reset the continuity and now the sum and the maximum value should be 20 from where we move on to the next element.

So in short, we need to take the maximum between the current element and the sum obtained by adding the previous sum to current element. If the current element is bigger, we reset the sum and the subarray. What if it is not ? What if the sum is bigger ? To get our answer , let’s consider the element 40, which is the next element in the array.

What does it mean if the current element is smaller than the sum obtained by adding current element to previous sum ? It means, the sum, the bigger value, can help us further as it has enhanced our overall value as compared to current element. It also means that the previous sum does not act as a deterrent and we continue with our sequence of elements.

Continue with the sum and the sequence since addition is an enabler and not a deterrent

So, in short, for every element in the array, we need to –

  1. Find the maximum value between the current element and the addition of the current element to the previous sum.
  2. If the current value is bigger, we need to reset. It will also give us a new value to the sum so that we can to continue our exploration further in the array.
  3. If the maximum between the two is the value of the addition of the current element and the previous sum, this value becomes the new sum.
  4. Once steps 1, 2 and 3 are done, remember, we need to maintain the max value like we did in the brute force approach.
Code for Kadane’s algorithm
public class MaxSumSubArray {

    public static void main(String[] args) {

        int[] arr = {30, -40, 20, 40};

        int sum = findMaxSum(arr);
        System.out.println("The maximum sum in the sub array is : " + sum);
    }

    private static int findMaxSum(int[] arr) {
        int sum = 0;
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            sum = Math.max(sum + arr[i], arr[i]);
            max = Math.max(sum, max);
        }
        return max;
    }
}

In the ‘for’ loop, we have simply translated the theory that we just understood into code. We find the maximum between the current element ( arr[i] ) at hand and the addition of the previous sum and the current element (sum + arr[i]). The one that has maximum value becomes the new sum.

sum = Math.max(sum + arr[i], arr[i]);

Once we have the new sum, we check if it is the new maximum and if it is, we assign it to the variable, max.

            max = Math.max(sum, max);

Did you notice that there is a single ‘for’ loop ? There are no nested loops ! The time complexity of this code using Kadane’s algorithm is O(n) which is better than the brute force approach. We only iterate through the elements of the array once. Does the code work for all inputs ? What if we supplied an array of all negative values ? Unfortunately, it does not.

Like the brute force approach, we have initialized the variable, max, to 0. One option is to assign it to Integer.MIN_VALUE, like we did in the brute force approach. There is another way to do it as well, the first element of the array can be assigned to the variables sum and max. We can then start our iteration from the 2nd element onwards.

private static int findMaxSum(int[] arr) {
        int sum = arr[0];
        int max = arr[0];

        for (int i = 1; i < arr.length; i++) {
            ...
        }
        return max;
}
Conclusion

We have seen 2 approaches to solve the problem of finding the maximum contiguous subarray. The first approach was simple but it had a time complexity of O(N2). On the other hand, Kadane’s algorithm has a time complexity of O(n), linear time, which is better than brute force. But, unless you know the algorithm before hand, it is difficult to come up with this solution at runtime, like, in an interview. But now I hope that after reading this blog, you will remember Kadane’s algorithm which is quite an effective technique to solve this problem.

If you still can’t remember the algorithm, it’s alright! I am sure that you will at least remember that the pronunciation is not ‘Kadanee..’ !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s