Hey there and welcome back.
Let's now get started with the very famous coding interview question called the Longest Increasing Subsequence.
So the question reads given an integer array Numb's.
Return the length of the longest strictly increasing subsequence, and we are given an example.
Let's say this is the array which is given to us.
So notice over here 12345.
So this is a subsequence of this array.
And it's in fact the longest strictly increasing subsequence.
And therefore the required output for this input is equal to five.
So this is the question.
Now it's very important that you understand the difference between subsequence and substring or subarray.
So if this is the array which is given to us for example, this part over here would be a substring
or a subarray.
Notice that nothing has been left in between.
Now if you want to delete this element and just take these two elements, it's not a substring or a
subarray, but rather it's a subsequence.
So in this question we have to find the length of the longest increasing subsequence.
Now that we have understood the question, remember, if you are presented with a coding interview question,
it's very important that you ask any clarifying questions that you may want to ask.
So a possible question for this question over here that you could ask is if an empty array is given,
does the output have to be zero.
And let's say the interviewer replies you won't be given an empty array.
All right.
Now if you have any other questions, make sure to ask them before you get started with solving the
question.
So we have understood the question and we have gone through any clarifying questions that we wanted
to ask.
Now let's go ahead and come up with a few test cases.
And remember, you can come up with test cases together with your interviewer.
And that's actually beneficial to ensure that both of you are on the same page.
Now, we've already seen one test case, which was the example which was given to us.
So if this is the input array, the longest increasing subsequence is of length five.
Now, if you're given an array with just one element, then the output has to be equal to one because
you just have one longest increasing subsequence which is this element itself.
And let's say the array is 3 to 1.
In this case, the output would again be one, because you can take either of these elements, but then
you can't take any combination of elements such that the elements are strictly increasing.
So over here also the output has to be equal to one.
In the next video, let's try to think what approach can be taken for solving this question.