Dynamic Programming — Kadane’s Algorithm

Swift Dynamic programming

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

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.

Dynamic programming