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?

Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs

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

Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

Gold Supporters: Micah Wood Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶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. ... https://www.youtube.com/watch?v=ggUN8TijNiU