Understand the FizzBuzz coding problem and its solution

Sort arrays in TypeScript

Case insensitive sorting for string arrays

Determine if two strings are an anagram

Determine if a string is a palindrome

Bubble sort using TypeScript

Quicksort algorithm using TypeScript

Insertion sort algorithm using TypeScript

Merge sort algorithm using TypeScript

Binary Search Algorithm using TypeScript

Find the repeated item in an array using TypeScript

Create random integers in a given range

Stack implementation using TypeScript

Queue implementation using TypeScript

Implement a singly linked list in TypeScript

Implement a doubly linked list in TypeScript

Parse a string to an integer

Shuffle an array

Implement the heap data structure using JavaScript

Find Max Items and Max Height of a Completely Balanced Binary Tree

Implement the Heapsort algorithm using TypeScript / JavaScript

Minimum / Maximum Maintenance algorithm implementation using JavaScript / TypeScript

Sum of the most common algorithmic arithmetic series

Median Maintenance algorithm implementation using TypeScript / JavaScript

Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript

Build Algorithms using Typescript

The maximum subarray problem is one of the nicest examples of dynamic programming application.

In this lesson we cover an example of how this problem might be presented and what your chain of thought should be to tackle this problem efficiently.

https://app.egghead.io/api/v1/lessons/typescript-maximum-contiguous-subarray-algorithm-implementation-using-typescript-javascript/subtitles

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.

Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript

Share this video with your friends

Course

Build Algorithms using Typescript