Longest Increasing Subsequence + Dynamic Programming

Here we introduce the "longest increasing subsequence" problem, which is, given an array A, try to find the longest length of any subset of A that is strictly increasing. I do an example in the video. It's easily shown then that the LIS problem can be solved in O(2^n) time by examining every subset. However, we can use dynamic programming here by noticing that "close" subsets are not going to have wildly different LIS values. So we develop a recurrence for the LIS problem, and then make an "iterative" algorithm that saves previous calculations in a table. We then show that it can be solved in O(n^2) time.

Chapters:
0:00 - Intro
0:39 - What is the problem?
5:04 - Brute force algorithm
10:05 - Can we go faster?
12:39 - Defining the recurrence
22:09 - How the memoization works here
22:57 - Iterative algorithm
33:05 - What is the runtime of the DP algorithm?

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Merch:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[tam]

Hi, cool videos. I've written this function, (made one based index array class to clarify), and it's working if in the first case, put return value to one, if not, giving me value less than one:

def LIS(xs, i, j):
if j > len(xs):
return 1
elif xs[i] >= xs[j]:
return LIS(xs, i, j + 1)
else:
return max(LIS(xs, i, j + 1), 1 + LIS(xs, j, j + 1))
print(LIS([0, 2, 3, -1, 2], 1, 1) # -> 3