Hello, guys, this is Andrea, a computer science teacher for today and today we are going to solve
another classic problem of dynamic programming approach, and that is the longest increasing subsequence.
So let's get into my statement.
All right.
You are given an array full of integers.
Could be positive or negative.
Doesn't really matter.
I call it a it's life is going to be end and you're supposed to find the longest increasing subsequence.
So you know what?
The subsequence it's a subset of elements not necessarily on consecutive positions and increasing means
strictly increasing.
So you can take a five and then take another five.
OK, now for this example, three nine seven, 14, 10, 12.
Obviously we have lots of increasing subsequence, but the longest one is elements one three, five
or six.
So value three, seven, 10 and 12.
First thing we should notice about this problem is that it's an optimization problem.
And when dealing with optimization problems, we should think straight ahead of two approaches.
The first one is greedy and the second one is dynamic program.
Let's take a look at the greedy approach.
Now, I don't know what which element I will start my subsequence, so let's say I am going to try them
all.
Let's start with three.
If I start my subsequence here, what would the greedy approach say?
Well, this is nine is greater than three.
So let's take nine into our subsequence.
Seven is less, 40 is greater.
Let's take 14 right now.
And then I don't have any greater elements than 14.
So this greedy approach would give me solution free.
But if starting from free and then taking the nine and then waiting and taking the ten and then the
twelve, I have a solution of Lamport.
So the greedy approach won't give me the optimal solution in the end.
So we should definitely solve this problem using the dynamic programming approach.
And as we know, when dealing with dynamic programming problems, we should use our bulletproofed formula.
So let's get into it.
OK, guys, step number one, we should define our sub problems and store the results using arrays.
Let's take a look at that example.
My initial problem is the Hornery.
I have to find the longest increasing subsequence.
So let's say I am a step n, which in my case is step six.
I have obviously two options for each element.
I should include it into the solution or not.
So if I choose to include these 12 into the solution now, I have to find the longest increasing subsequence
from this and minus one element if I choose to include then from this and minus two elements and so
on.
So initially I could think of something like this.
I can say DEPI of I the longest increasing subsequence.
It's going to be abbreviated like this of the first element.
So eight from the first element of the element.
OK, but there is a problem with this approach because I don't have enough information.
And let's take a look if I was to proceed and go to step two.
So let's see.
Here I am on step two, as we know, step two, we should find our recurrence relation.
And let's say I want to compute P of I find the longest increasing subsequence from the first elements.
As we said, two options I take or I don't take the element into the solution.
Let's say I take it if I want to take this element into the solution, let's say 12, I'm going to have
one, obviously, and the length from this element plus.
What do I have to write here, because I should definitely take the longest increasing subsequence now
from the first I mean, this one element, so this could be something like deep of a minus one, but
there's a problem with that.
I don't know what's the last element of this solution, let's say?
Here.
Instead of seven would have been an 11 if he would have been an 11 DP of five, only these five elements
would be four and that would be three, nine, 11 and 14.
That would be the solution, and I say one plus four divisions, five, so I take these four elements,
three, nine, 11, 14, and then add my 12, which is not correct, because 14, the last element of
the solution is greater than my element.
So I can do that.
So that means that this information is not enough.
I need to know the lease of the first element and what is the last element.
I should add another restriction DP of I is going to be the least of the first elements and I make sure
that I am going to use in my solution this I element.
So the list of four elements and last element of the list.
Last element is.
A guy that is the restriction, I will always use this last element in my solution.
Now, if I wanted to conclude this one, Deepavali and step two, we just find the recurrence relation.
I have one plus.
If I choose to do dippie of I minus one, that is cool because let's say again, this was 11, OK,
this was 11, this deep of minus one.
So this element, could it be now three nine, 11, 14, because it has to end with the fifth element,
which is 10.
So worst case, it could be three, nine and 10.
And then I can add 12.
OK, so as we've seen, we are now using the F element in our solution.
So one plus.
But this shouldn't be DEPI of a minus one because the element before the last one could be each element
from positions one to position ie minus one.
That is actually less than this last element.
So I have to take now the maximum of all these possibilities and those are deep of G where one is less
or equal to G, which is less than I and very important aguy should be less than eight.
Now this is the very recurrence relation.
I try out every element that could be before the last one and I take the maximum of these debates plus
one from my last element.
Step two is now completed.
OK, guys, now we've finished the hard part.
The last three steps are actually easy.
Step number three is defining the order in which we should solve our problems.
So let's take a look at the recurrence relation in order to compute the answer for this.
Some problems, I already need to have computed the answers for some problems that have this G less
than my.
So all I have to do is confuse them with I increasingly from one to an increasingly OK, and that should
be the order of the sub problems.
Now four step four.
Let's take a look at step four, initialize the non computable states.
So again, I take a look at step two for computing dippie of I.
I need states that have this gayed less than my own.
So the only problem would be when this is going to be zero because I have no states, less than zero
of minus one minus two doesn't exist.
So I only have to do DPE of zero is obviously going to be equal to zero because I have no elements to
take into the solution.
So step five, as you know, we should find the answer of the problem and we will be a little bit tempted
to say that the answer of the problem is DEPI of N.
But remember when I say DPF and that means that I am going to use as my last element n and that's not
always the optimal solution.
So I'm going to take the maximum of all the piece, actually the P of I where I is going to be from
one to position, and this is going to be the answer of the problem.
Now let's take a look at the time complexity for this problem where we have and solve problems that
we wish to compute right from our problem.
One, to solve problem and but for each cell problem, in order to compute its answer using this recurrence
relation, we will use another forum and iterate through every that is from one to eight minus one.
So we will have two nested for loops in order to compute all the answers for the sub problems.
And that is going to be big o of and squared memory.
Of course it's going to be big O of F, so this solution is not quite very fast because they make time,
complexity of bigo of squared.
If you want to take a look at the code for it, it's actually really simple.
Again, as we did on the last problems.
We just.
Define this already be globally, then initialise DP zero equals zero, use this for loop I from one
to n i plus plus then the recurrence relation which you use another for an apology from one to a minus
one G plus plus.
And if this, A.J., is less than eight, we update the DP of eight and after that another for loop
to compute the maximum.
But the optimal solution is actually in big O of and log in time complexity.
And it's basically the same solution.
But we use a trick with another array.
So I want to clean the whiteboard and in the next chapter we will solve this problem in the right time.
Complexity.