Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript

Instructor: [00:00] Given an array of n numbers. We have to return the contiguous subarray that has the largest sum. For this simple example array, the answer would be the subarray {4, -1, 2, 1} with the sum of six.

[00:19] An i solution would be to simply check all possible subarrays. There is of the order of O(n) square, as you would loop through every starting point, and for every starting point, we would check every possible tailing end point.

[00:36] We can actually get a much better linear solution with two key observations. First, the maximum sum for any subarray in the range 0to i, when the element at i must be included can be represented as the maximum including i-1 plus the current value.

[00:58] Of course, if the maximum including i-1 is less than zero, there is no point in including that in the sum, and you should only use the value at i. The second observation is that the overall max sum for the subarray 0to i irrespective of if the ith item is included or not, can be represented as the larger of the max at i-1, or the max of when i is included.

[01:31] Combining these observations, we have these two neatly written down relations. One for the max including i and one for the overall max at i, irrespective of if i is included or not. Notice that up to index i, we know the answer max i immediately, if we have the max including i-1 and the max of i-1.

[02:00] The answer up to i only depends on values that appear earlier in the array. When a problem can be solved, given someone gives us a pre-solved answer to a subset of the problem, the problem-solving approach is dynamic programming.

[02:17] The optimal answer at i depends on optimal answers for i-some constant, and the problem is said to have an optimal substructure. A key trait of dynamic programming algorithms is that they can be solved with the simple table.

[02:35] Let's solve the example array by hand to demonstrate this tabular approach. At element-2, the maximum including it would be -2, so the maximum we can hope to achieve is -2. At element 1, the maximum including it would be 1, as there is no point in including the previous -2 and the overall maximum is 1.

[03:01] At element -3, the maximum forcefully including it would be -2, as we should include the previous maximum including of 1. However, since this is less than the previous max, so we wouldn't include max including into the net max.

[03:20] Let's just fill out the rest of the table little bit faster. You basically just follow the two formulas for max int and max at each step. The sum of the maximum subarray for when all items have been considered is simply the value at the max column for the last row.

[03:41] We could store the table like this in O(n), since it is just two additional arrays. Using this table, we could also potentially easily derive the maximum subset array that give us the final max value.

[03:56] However, we can do better than keeping this full table in memory, by keeping track of a few variables. We simply observe that the subset max array would start at index i, if the value at i gets copied to the max section.

[04:12] This indicates that this value is greater than any max we had seen so far and essentially starts a new max subarray section. The subset max array would expand to include index i, if max including gets copied to the max section which indicates that this i is in the tail of the max solution.

[04:36] We now have a firm understanding of the problem, and we can code it out as a simple iteration from 0to n. This is another trait of dynamic programming algorithms that you normally use iteration instead of recursion.

[04:50] We start off with the simple function that takes an input array and returns the max contiguous subarray. If we have an empty array, then we go ahead and simply return an empty array. Next, we go ahead and initialize our loop invariants max including max, max start index, and max, and index.

[05:16] Next, we simply loop through the elements in the array, keeping track of these invariants at each iteration and using their previous values to calculate new ones based on the relations that we have already figured out.

[05:37] Once the loop terminates, we simply return the max contiguous subarray as the slice from the original array using our calculated max start and max end indices. Since this algorithm only does one pass to the input array, it has a linear of n time complexity and a constant space complexity of O(1), as we are only maintaining a few variables to track the invariants.

[06:05] Let's go ahead and call the function with the example input array. If we go ahead and run the code, you can see that it works as expected giving us the maximum contiguous subarray.