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.
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
let sum = nums[start…end].reduce(0, +)
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.
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.
var mem = Array(repeating: 0, count: nums.count)
By definition the first element of this mem is the same as the input array
mem = 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
This is Kadane’s algorithm!
The algorithm states that:
maxSum[i] = max(A[i] + maxSum[i — 1)
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).
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: