# Dynamic Programming — Kadane’s Algorithm

## Swift Dynamic programming

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

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

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:

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

Written by