Maximum Subarray Sum using Kadane's Algorithm

This is part 1 of the DSA series where we will be going through the Kadane's Algorithm to solve the 'Maximum Subarray Sum' problem.

Let us first understand what a subarray is. Consider the following array of integers:

int arr[] = {7,2,0,5};

A subarray is formed when we take an element from the original array and pair it up with every element. Here are all the subarrays (separated by spaces) of the array arr:

[7] [7,2] [7,2,0] [7,2,0,5]

[2] [2,0] [2,0,5]

[0] [0,5]

[5]

Note that [7,2] is the same as [2,7] and it applies for all elements, hence we didn't include that. Let's have a look at the problem

The Problem

Consider we have an array of n integers. Our task is to find the sum of each subarray from the original one and print the maximum sum.

Going back to our previous example and calculating the sum for each subarray, the maximum sum comes out to be 14.

So here is a breakdown of the question:

1. Create subarrays from the original array

2. Find sum of each subarray

3. Print/return the maximum sum

Let's move on to the solution.

The Bruteforce Solution

Our first task is to create subarrays. One way to look at it is to have a starting point or starting index & an ending index and then printing all the elements between the starting and the ending index. Let's take an example.

This was our array: int arr[] = {7,2,0,5};

Consider the starting index to be 1 and the ending index to be 3. If we print all elements between the starting and the ending index, i.e., arr[1] till arr[3], we will get the subarray, [2,0,5]. Similarly, we can get all subarrays and their sum by this method using nested loops.

Below is the code using 3 nested loops. This is the brute force method. Feel free to dry run the code for better understanding.

for (int i = 0; i < numbers.length; i++) { // i is the starting index
    for (int j = i; j < numbers.length; j++) { // j is the ending index
        int sum = 0; // variable to store the sum of each subarray
        for (int k = i; k <= j; k++) { // k loops between indexes i & j to print all elements
            sum += numbers[k];
            System.out.print(numbers[k] + " ");
         }
         System.out.print(", Sum of the subarray is: " + sum);
         System.out.println();
     }
     System.out.println();
}

Solution Using Kadane's Algorithm

Finally, looking at the most optimised way to solving this question. The previous code does work but we didn't work with negative integers in the array. Also it is inefficient in terms of time and space complexity.

So now, consider an array of positive as well as negative integers.

int arr[] = {7,9,-8,-5}

Kadane's Algorithm basically says that while calculating the sum of each subarray, if the sum becomes a negative number, we assign it as zero. This is to avoid adding anything to a negative number and considering it as zero altogether because its no use adding anything to a negative number. The maximum sum is going to be positive anyways (except for a corner case which we’ll look into further). This simple step saves us from performing unnecessary steps.

So, if you write down all the subarrays and their sum, you'll notice negative values such as -4, -8, -13, etc. too. The algorithm says that whenever the sum is a negative value, change the sum’s value to zero and continue adding. This works when the original array is a mix of both positive and negative integers. So far our code looks like this:

int max_sum = Integer.MIN_VALUE;
int currentSum = 0;

for (int i = 0; i < numbers.length; i++) { 
    currentSum += numbers[i];
    max_sum = Math.max(max_sum, currentSum);

     if (currentSum < 0) { // if currentSum is negative, change its value as zero
        currentSum = 0;
     }
}
return max_sum;

Corner case

The algorithm works great so far. But there is a corner case we haven't checked yet. What if all the integers in the array are negative? The current approach will return the maximum sum as 0 (go ahead and try with an example) which would be wrong. The simple solution is to first check if all the numbers are negative or not and then proceed. The code is as follows:

min_sum = Integer.MIN_VALUE;
for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] < 0) {
        min_sum = Math.max(min_sum, numbers[i]);
    }   
}

This was an interesting problem and I learnt a lot. More to come :)