Dynamic Programming — Kadane’s Algorithm

Swift Dynamic programming

Image for post
Image for post
The example maximum subarray

LeetCode 53 has many solutions, some of which do not pass the aggressive time bounds on this problem.

The challenge

Given an Integer array, find the contiguous subarray with the largest sum.

The brute force solution

For each start element in the input array, calculate each possible end element in the array and calculate the sum.

In Swift I have chosen to use functional programming to calculate the sum of the subarray

although other methods are possible

This solution is O(N²).

Each end point is visited multiple times, and might not have the optimal start point for that end point.

The issue is that we need to save the previous computation to be used for our next possible end point.

Dynamic programming

We can take each element of the input array, and see that there is a maximum subarray for each possible endpoint in the array

Image for post
Image for post
An example of the process to calculate the maximum subarray

We will call the maximum subarray with this end point “mem” as is the convention in dynamic programming. As in the example above, this will be the same size as the initial array.

By definition the first element of this mem is the same as the input array

then we iterate through the possible end positions of the array.

For each, the maximum is either the new sum (which itself is the current number added to the previous running sum), or (if larger) take the current number as the new sum

Maximum sub array

Kadanes’s algorithm

This is Kadane’s algorithm!

The algorithm states that:

Since the maximum sum of a sub-array ends with A[i] is always either itself, or itself added to the previous maximum sub-array (taking the greatest of the two).

Improvements

1. We can calculate the maximum of the array as we go.

2. In fact we don’t need to calculate the whole maximum subarray. Instead we can do this “as we go”! This gives us the following:

The complete solution

Want to get in contact? Get in touch on Twitter:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store