# Maximum Sum Sub-array Problem: Kadane's Algorithm

The problem presented is that you have a one dimensional array of numbers. From that array you need to find the maximum sum sub-array. The sub-array must be contiguous.

The solution to this can be in several forms. You could just want the actual maximum sum of the numbers. In this case you would find the sub-array and then sum all of the numbers and return the value of the maximum sum. Another solution could be that you want the elements of the sub-array. Finally, perhaps you just need to provide the indices where the sub-array starts and ends.

There are several ways you can implement this solution.

- Brute-force. Just look at every possible combination and choose the best one.
- Divide and Conquer. This approach will divide the problem into a smaller problem and solve the smaller problems.
- Kadane's algorithm.

Here we explore Kadane's algorithm.

## Compute Maximum Sum

Presented with an array of numbers, find the maximum sum sub-array.

Kadane's algorithm is an optimized method of scanning the array to find the largest sum sub-array. Like the brute-force method it iterates over the array to find the maximum sum. However it does it using a single loop which improves the performance.

```
maxSum = 0
currentSum = 0
// Iterate over the array
for (i = 0; i < array.length; i++)
{
// add current index to sum
currentSum = currentSum + array[i]
// Is the current sum less than zero?
if(currentSum < 0)
{
// Reset the sum and subarray indexes.
currentSum=0
}
if(currentSum > maxSum)
{
maxSum = currentSum;
}
}
return maxSum
}
```

In addition to only having a single loop this algorithm has another change from the brute-force method. It resets the `currentSum`

to zero if it ever drops below zero. This is the key to this algorithm. If the `currentSum`

is ever less than zero then you can safely discard the entire sub-array that you have built up to this point. Any values to the left of the current position will only result in a smaller sum no matter how large the positive values are remaining in the array.

Finally, the `currentSum`

is compared to the `maxSum`

and a new `maxSum`

is assigned if the `currentSum`

is larger.

If we use our example array towalk through the algorithm this is what we see. First the iterator starts with position 0. This results in a sub-array of length 1 with a currentSum of -1

The `currentSum`

is found to be less than zero and so the `currentSum`

is reset to 0. Since the `currentSum`

is not greater than the `maxSum`

the loop continues and increments to the next item.

During the second time through the loop the array[i] value of 3 is examined. The `currentSum`

is incremented by 3 resulting in a value of 3 since we reset the `currentSum`

to zero during the previous loop. The currentSum is not less than zero so we do not need to reset it. The currentSum is greater than the current maxSum and so the maxSum is now set to the curentSum and the loop is incremented to the next element.

The array[2] is now being inspected. The value of this is added to the currentSum and results in a value of 1 since the value of currentSum is 3 and the value of array[i] is -2.

The loop continues to inspect the next element in the array and add it to the currentSum. Each time the currentSum is larger than the maxSum it is assigned to maxSum.

After reaching array[6] the maxSum is currently set to 6.

The array index is incremented to the next two elements array[7] and array[8]. Each time the currentSum is insepcted it is found that it is less than the maxSum. After inspecting all of the elements it has been determined that the maxSum is 6.

## Analysis of solution

The solution must iterate over the entire array before it can determine the maximum sum. However it only needs to do this one. This means that the time for this algorithm to complete it will take `N`

iterations. This results in a complexity of O(n).

## Negative Numbers

The algorithm as it is presented will not work if all numbers in the array are negative or if the highest value item is a zero. A minor change to the algorithm can remedy this though. Set the initial `maxSum`

to `MIN_INT`

to represent the minimum value for an integer. Secondly, move the check for a currentSum less than zero to after the maxSum is set.

```
maxSum = MIN_INT
currentSum = 0
// Iterate over the array
for (i = 0; i < array.length; i++)
{
// add current index to sum
currentSum = currentSum + array[i]
if(currentSum > maxSum)
{
maxSum = currentSum;
}
// Is the current sum less than zero?
if(currentSum < 0)
{
// Reset the sum and subarray indexes.
currentSum=0
}
}
return maxSum
}
```

Now imagine an array where ALL of the values are `MIN_INT`

. With the maxSum now set to the minimum value for an integer any value in the array is guaranteed to be greater than or equal to the maxSum. If the first value in the array is the `MIN_INT`

then the maxSum will remain `MIN_INT`

. The currentSum will be reset to 0. At each iteration, the value of currentSum will be found to be less than or equal to the maxSum and therefore the maxSum will not change.

After all of the array values have been inspected the maxSum of `MIN_INT`

will be returned.

If there is an array where at least one of the values is greater than `MIN_INT`

then the currentSum will be greater than maxSum and it will be set accordingly.

You now can compute the maximum sum sub-array in O(n) time and process an array with all negative values or a mix of negative and positive.

You must be logged in to see the comments. Log in now!