[00:02] You're given an array and asked to find the length of the longest increasing subsequence. Not sub array, but subsequence. So importantly, the numbers do not need to be next to each other. Take this example.
[00:15] The answer here is four because 2 4 6 and 12 are increasing. Most people try to build all subsequences, but it gets exponentially worse. Instead, think like this. For every single number, check what
[00:29] increasing subsequence can end here. We know that every number is at least a subsequence of length one by itself. Now look to the left. If the current number is bigger than a previous number, it can extend that subsequence. So for
[00:43] each position, take the best valid subsequence before it and add one. Now watch what happens. At four, it can extend two. extend two. At six, it can extend two, four, or
[00:56] So you pick the best one. That's dynamic programming. You're not generating everything. You're reusing the best answer ending at each position. And in the end, the biggest value you built is the answer. Like and follow for more DP
[01:11] the answer. Like and follow for more DP problems.