What's going on, guys?
And here we are continuing the from zero to hero journey with a special problem, which I think is the
perfect introduction for you guys who are beginners and the dynamic programming approach chapter and
want to learn more about this.
So we are going to see how to approach these kinds of problem.
I'm going to give you a bullet proof formula for solving these kinds of problem.
And we are going then to write the code together.
So stay with me, guys is going to be awesome.
Consecutive some sequels is called and let us read the statement together.
You are given an integer array of love.
And you have to choose some some sequence of this array of maximum length such that this subsequence
forms an increasing sequence of consecutive integers.
Right.
So in other words, the required sequence should be equal to some X, X plus one that that that X plus
K minus one for some value X and level K.
So first of all, what is a subsequence subsequent someone rate, as they say, can be obtained by erasing
some possibly zero elements from the array.
Then you can erase any elements.
Not necessarily going successfully.
The remaining elements serve their order.
All right.
This is important.
For example, for your eight five three, one, two, four, the following arrays are subsequence is
free.
Five, three.
One, two, four.
Like the whole array.
Right.
Five.
One four.
One free is not because if you take one free, one is a position free and frees a position too.
And you can't swap the positions.
You have to maintain the road.
Superimportant.
So let's take a couple of examples.
Thomaston better the statement.
Right.
So again, very simple here.
And going to take my notepad.
I'm a classy guy.
And let's take the summary.
Free, free.
Four, seven, five, six and eight.
Perfect.
What the answer is for.
So the lamp is four.
And it looks like there some sequence is forming, is formed by the positions to free five and six.
So that position two, we got a free at position free.
We got to for that position five.
We got the value five actually at that position six.
We got the value six of five here and six here.
All right.
So as you can see, this subsequence is basically subsequence of values which are increasingly and consecutives.
Right.
Free for five and six.
Right.
For the second example.
If you take a look at this array, which is one three five two four six one three five two four six,
the solution is two.
And it's only formed by the positions one in four.
Right.
So value one position, one add value to a position four.
Right.
So this is.
Yes.
All right.
Now you know what is a subsequence?
You know that the elements should be increasing and consecutive.
Let's think of some brute force approach.
But first of all, I'd like you to notice that when we want to find this subsequence right subsequence
formed by increasing consecutive integers, this subsequence always has to end somewhere, right?
It has to end at some position.
So.
We are going to solve this using dynamic programming approach.
And very important step one, when solving each dynamic programming approach.
I'm going right here to step one is to figure out what is the information you want to host.
Right.
So find out the information you need.
Usually this information is going to be stored in memory using arrays, right?
Could be one dimensional, two dimensional, three dimensional.
It's just based on the complexity of the problem.
So we are going to start here.
Easy, because we just have an array which is one dimensional.
So we are going to have your DEPI of AI.
Right.
It's an array.
Only one dimension.
And what should be this answer?
Right.
This is the most important question.
Well.
Let's think about this.
If I won the subsequence, it obviously has to end somewhere.
So I'm interested in what is the last position of this subsequence, right.
Where does the subsequence at.
Sorry.
TDP of I.
Right.
Always you take those parameters that you need and put it as dimension's in.
So deeply, IVI is going to be basically the statement of the problem.
So the max length of some valid subsequence I'd say.
Right.
Which ends.
Which ends in position.
Right.
So it ends a position.
Right.
Perfect.
Step one is now done.
We know what we need to compute.
Which is awesome.
Because if we manage somehow to smartly compute disarray, what is going to be the end sort of the problem?
Well, this is the step two.
Step two is figuring out if you know how to solve this array.
It's not gonna be useless.
So you know how basically to get the solution of the problem.
And it's pretty standard, right?
Because for the length, you are going to take the maximum between DEPI of one of two to be a free.
And so on until DPF.
Right.
Because you're subsequence could end at any position.
You take the maximum out of this.
Perfect.
Now step one down.
Step two completed.
It's time for step three.
We know what we should compute.
So the step three is obviously how to compute it.
Right.
So step free.
Right.
So step two, let's right here is find out the answer, which we know is going to be this one.
Perfect.
Now, all right.
Four, step three.
We need to find out how to compute the DP.
At this, we are going to need something that's called the recurrence recurrence formula.
I think something of that.
OK.
So deeply of the recurrence formula is based on the following theme.
You want to compute this information.
This current state, which is DEPI of I using states that were already computed in the past.
Right.
So let's say I want to compute disarray starting from position one all the way to position.
And when I want to compute DEPI of I, I know that I've already computed DEPI of one, DEPI of two dot,
dot, dot until DEPI of minus one.
Right.
So I want a formula based on those values that are already computed.
And let's think about this.
When I have DPL I.
I basically know in what position my subsequence would end.
Right.
So let's take our example of free, free.
Four, seven, five, six, eight.
And let's say I want to compute.
I don't not DEPI of six.
Right.
So when I want to compute DPF six, let's take the position six positions.
Six is this element, which its value is six.
So I know that if that's the last element, the previous element has to have a value five.
And its position is going to be on my left.
Right.
So I can try out every position starting from position one all the way to position ie minus one.
And if that element has a value, which is my value minus one, that means it's a possible previous
element for my sequence.
Right.
So 40 B of six.
In this example is going to be DEPI of five because that value five is a position five plus one.
Right.
Because eight of five, as we said, is equal to a six minus one.
Right.
So the general formula is DEPI of I.
He's going to be some DEPI of G.
Right.
Some position plus one where.
Very important.
A of G is going to be equal to a of a minus one.
And one is less or equal than J minus or equal dng.
Which is less than I.
Right.
So perfect.
Now we have a recurrence relation.
We can make a for loop and try each of these GS from one to a minus one.
And for each valid one we can update our DEPI.
So deeply of I as we said from all our JS.
What is going to be like we can have multiple possible valid JS, right.
And for each J its formula is DEPI of J plus one.
So what should we choose between all these options.
Well what does our problem ask us for the maximum length.
So we are going to choose the maximum value from all this possible value.
Right.
So I'm going to have your maximum between DPF J.
Right.
We have one less or equal than J.
Less than I and a of J is equal to a of I minus one.
Everything plus one.
Right.
Because that plus one is a constant.
We need to take this Max.
DEPI of J.
For all the villages.
Perfect.
Now we know how to compute our array.
Step four is basically a very tight two step free because we need to know in which order we will compute
these debates.
Right.
And how we know that is super simple.
We look at the recurrence nation and we see that.
Okay.
In order to compute my DEPI of I, I see that I need the maximum between DEPI of JS where G is between
one and I minus one.
So I need to have computed already all the Debby's we've positions on my left.
So find out the order in which you compute your information.
And this order is going to be starting a position one go into position two, free and so on until position
F.
So my order is going to be DPL one first.
Then the B of two.
Then NDP are free and so on.
And when I should compute DEPI of I let's say I got everything that I need.
Perfect.
And I got a step free regarde station.
I got a step for the Wardour which is perfectly you compute your rate and you have your answer.
Now what is the time complexity of this algorithm?
Let's think it like this for the time, complexity, time complex.
We are computing and values, right?
So we are computing and values or how I like to call it and states.
Right.
So values or states.
Perfect.
Now, for each state, in order to compute it, we look at the recurrence relation and we try each J
out.
So we are making a fourth group.
Right.
So basically, what do we do here?
Well, first of all, I got this for loop.
We have I started a position one less or equal then and I proposed.
And when I want to compute.
So for computing DEPI of I, I make another for loop.
Right.
So four into G equals one G.
Less than I j plus plus.
And if this a of J is equal to a of I minus one.
What do I do.
I update my DEPI of I dpa vi is going to be the maximum.
Between what it already was and this new possible value which is DEPI of J.
Everything plus one.
Right.
So it's pretty obvious that we have two rested for loops.
This is a brute force approach, guys.
And its complexity is bigglesworth and squared.
But we still have something.
We have a brute force approach.
And from this approach, that's why I love to start to brute force approaches.
They are super amazing because most of the times you can start from there and figure out, all right.
I just need to do that and I'm going to have the perfect approach for the problem.
So let's think about how to optimize this, because the optimal solution is going to be biegel of.
Right.
This is why you have having the restrictions.
If you check those out and less or equal, then to cross 10 and power five.
Right.
Because you need linear solution.
So optimal solution because.
We are going to take the fundamental solution for the brute force approach.
This dynamic programming approach.
But we are going to be smart about it and we should break it down to two things.
Why is my complexity bigger event squared?
Well, it is because I have to compute and states and for each state.
I got a bego of re car Riccardo's relation.
All right.
That was the what relation of forming.
But it's OK.
So I have M states, so n times I have to perform a bigger lavada recurrence relation.
So in order to make this bigo of N total time.
I have two possible choices.
First of all, I won't compute any states.
I will compute only one and perform a Bego bingo, a rigorous nation for that.
Right.
So I can have one state crossed bigo of any relation, regardless relation.
And this is a bigo event.
Or I can have any states and a beagle was one Konstantine recurrence relation.
Those are my possible options now for the first option with one state.
That's not quite smart, and that's not quite possible because.
I have to try each position out, so for my subsequence.
I need basically to fix what is the last element of this.
So I can't just guess.
OK.
It's going to be dispositions.
That's the one I have to basically go and try each position outright.
So any state is going to remain there.
But.
Can I be smart about it and make it from legal event to a bigger wild card insulation?
And I can't.
And how to do that?
Well, let's take a look at my record restoration.
It's the maximum between this DEPI of J.s.
We've J from one point minus one and A of G is equal to a of a minus one.
So.
What do I need to know really fast?
I need to know the maximum between all these DEPI of GS that I have already computed.
Right.
Because when I when I am in this for loop, in this first for loop, when I am at step, I, I have
already computed everything between one and I minus one.
Right.
So I have gone through all my possible GS for all my possible DEPI of GS, but I'm going to need here
the maximum between all of this.
But we have the property, only those of the property that AIG has a special value and that value is
a VI minus one.
Right.
So.
The following idea comes to my mind.
I should have.
Somehow, pre computed, pre computed means, before I even perform this recurrence relation, I should
have an information like this.
I should have another.
Max DEPI and Max DEPI should meet Max DEPI of some X, let's say, is going to be the maximum between
DEPI of GS with the property that A of J equals X.
If I can compute and have fast this information, I'm done because the maximum between.
So as we said here, DEPI of AI is equal to the maximum with NDB of J.
Or everything plus one.
Perfect.
But this maximum between this DEPI of GS is now going to be Max DEPI of.
And you guessed it a of AI everything A of AI everything minus one.
Right.
So I'm taking this DEPI of GS into consideration.
I taking their maximum and then add one.
I only need to have computer disarray.
And this array is going to be computed along with my DP.
Right.
Because basically disarray is computed using the Debby's so along when I compute the DPRK, I will compute
disarray.
And let's think about what is going to be it for me.
So how this array is updated.
What?
If I take a look here in this main for loops, right?
Well, where I am in this for loop.
And I finish computed, right, let's say, here.
I have finished computing, finished computing, my DEPI of I right.
I have finished computing it.
It's done.
I know its value when I know its value.
I should update my Macs DPRK in order to use it for my further steps.
So, Max, DEPI.
Well, what is the new thing here?
When I computed the DEPI of AI right.
I have this new value which could affect my Arae Max DEPI.
But where can he do this?
Well, Max, the P of X is the maximum.
Between DEPI of JS where A of G is equal to X.
So I need to go to this value to my ay of AI here.
And at this position I should update the Marks array.
In case this DEPI of AI is greater than what already was the value in Max DEPI.
So let's debate is now the maximum between Max DEPI of a of AI NDP of AI.
Right.
Does it make sense?
It sure does.
Right.
It should do, because now I know the max to be sold when I have finished computing DEPI of I.
I update my Max Dibia array, which can only change in the position of I.
And now I can go here in this for loop 4G and move the for loop, because what do I do now?
I know that.
DEPI advice is equal to what I want to post this video and think about what should I write here?
After it do this, it's Max DGP.
Well, my A of G.
Should have been equal to of minus one.
So Mexia B of A of minus one.
Plus one.
So now I can compute is DPF I.
This is bigger with one.
This is Konstantine.
And after I do this I can update my mux DPRK stealing Konstantine.
So this is Bego 012, which is super amazing guys.
I have only one for loop.
I have extra memory because I use an extra array, which is Max DEPI.
But I can know what is the value of DEPI of I in Bigo of one.
And I can update my Moxley before further use for further computing my tepees in Bigo of one.
And this is how we get the solution in beadell of NGOs.
Now let's think about our output.
We should output the maximum length and.
Furthermore, we should output the position of our optimal subsequence.
Well, how do we do that?
The maximum love.
What do we said?
That's the answer.
Look here is going to be the maximum between DEPI of one dippie of two, your free NDP of X, right.
So let's assume that when we computed the answer, this answer is some DEPI of B, right.
So at position B, we have the maximum DEPI value.
And this is the answer ODP of B.
So we bring DEPI of B.
Everything's OK, but we still need to print those indexes.
And in order to do that.
We are going to need one more information, and that is OK.
I know what is the last element, right?
I know my subsequence ends up position.
But what is the previous position?
From the solution, I should know that, and I can only know that.
While I compute DEPI of Eyes very so we will have another extra LRB, which is going to be the previous
element.
So my arrays will be my arrays will be DEPI of our Max.
Right.
Max dippie of our Max and I will have another array, which is going to be less a previous element.
Previous element of.
And Max.
Right.
And think about this when I compute DEPI of IIs Max dippie of AA minus one.
Plus one.
Basically what we do here is I take that J that previous elements position and then I add my position
to.
Right.
So I should know that J.
Well in order to know that J.
In my Max DEPI.
I know the value.
I know the maximum value.
I should know.
What is that position for that maximum DEPI value that I'm looking for?
Right.
I'm not gonna need only the value in order to know the DP.
I'm going to need the position to in order to know the proof element.
So what I can do here basically is change a little bit.
The meaning of Max DEPI.
So here, Max, the P of X, right.
Let's take it from here and put it right here.
Max, the P of X, instead of being the maximum DP of J with A.G. equals X, which is good.
Let's change it from being the value to being the position.
So let's change it to be something like this, to be that G.
Right.
Some G where a G is equal to a minus one, obviously.
Right.
And that G has the maximum DP of all.
So this DP of G is actually the maximum between all this DP of JS, let's say.
Right.
We have this J.
So all this DEPI of J.
Let's say G prime.
All right.
G prime.
Where a of G prime is.
A minus.
Right.
So what I basically did here is instead of holding the value of that debate, we now hold its position,
right?
Perfect.
Not when we know this position.
DEPI of AI is not going to be Max DBI of a of AI minus one.
This Max GDP is now going to hold us the position.
So in order to get the value to get the DP from that position, we will need DEPI of this Max DP.
Perfect.
Now we have computed the DP.
After that, we need to update our Max DP.
But it's not anymore.
The maximum between what it was and DP of AI.
I need the position.
Right.
So if this value DP of AI is excellent is actually greater than what was the value of the max DP.
My current Max DP.
So DP of Max.
DP of Alewife.
Right.
If now I found a greater value.
This is perfect because I can say that Max DP of A.I. is going to become PI.
Right.
So the position with the greatest DP of AI, which is valid for the value A.I., is not going to be
AI.
Which is perfect at.
Both the regional and think about what is going to be the value of Prešov element.
What is going to be very precious element of I is going to be equal to Max DEPI of a of a minus one.
So Max B of A I everything minus one.
Right.
This is going to be the prev element of pi.
So we have computed our DP.
Taking the position from Max DEPI of AA minus one.
We have completed the previous element, taking the position from max of AA minus one.
We have updated our next debate.
Perfect.
We have everything that we need here now.
And this is a guys.
We know how to compute the answer.
We know now how to build our answer.
Subsequence.
Everything in your time.
And we basically solved our first dynamic programming problem.
It is not an easy one, but it's very nice for the introduction because it has a lot of concepts.
Right.
So we are starting from the Butros approach.
We are going to a linear time approach.
And we even find out how to build that subsequence.
The code for this problem is going to be great, is going to be interesting, and you are going to learn
a lot of things from it.
So I am very excited.
I don't know if I should keep it for tomorrow or for today.
But please, if you like this video or subscribe to this channel.
Hit the like button.
And let's say at 50 likes, we are going to post the implementation for this problem.
I know it's cheesy.
I know every one does that, but you are definitely going to take a lot of value from the implementation.
So really, all the channels to the problem really have the two enjoyed it.
Don't forget to join our Facebook group in which I will post along with my moderators challenges every
day or bits of wisdom or maybe something from our experiences in competitive programming or interview
questions.
And we are going to grow as a big community and sharing ideas all around the world.
Maybe this is the point.
And again, this was Andy.
I hope that you enjoyed the problem and they will see you in the day free of from zero to hero journey.