Its worth to appreciate the hard work. Any one can easily see him so exhausted after doing the daytime job at Apple. But he still makes these helpful videos. Kudos!
Intuition behind this solution: If the current element is greater than the previous element, we can safely add 1 to the value of previous max sum. Since the previous max sum was also calculated in a similar manner (optimal substructure) we can safely add 1 to previous max value to get the current value. If you notice in case of 6, since it is greater than 0, you can add 1 to the max value at 0. But there is a catch, you can have previous elements (for example 4) which can give you a bigger subsequence. Hence to check this, every time the "j" begins with zero. Or you can even start at the given i and keep going backwards with a j variable to check if there are two or more contending elements which can give you the max value. Notice how we construct the solution from using the previous solutions (previous values in array). This is in essence Dynamic Programming where you remember the previous computed values and make calculations faster. PS: please correct mistakes if any.
I agree that explaining the recursive or iterative brute force method first would be better. Doing so would help with making the connection from how you would solve the problem naively, to how you could use dynamic programming to solve it faster
This is the recursive solution def li_seq(arr): if not arr: return 0 if len(arr) == 1: return 1 count = 0 for i in range(1,len(arr)): end_at_i = li_seq(arr[:i]) if arr[-1] > arr[i - 1]: count = max(end_at_i + 1, count) return count
he wont do this cuz solving this problem by recursion it would take too much, just imagine that if u give a super long subseqvence it can take up to some months for your computer to find the solution, the best 1
Really really great explanations, thank you very much. Just one suggestion : I thoroughly understood the solution but still I don't know the intuition behind coming up with this solution. Could you please explain that also? Oh And the time complexities as well. thanks again :) :)
The intuition here is like an eye ball movement. Let's say you have a simple array [1,2,4]. The answer is 3. How ? In the eyeball movement you see the number 1 then register in your brain 1 . When you go to the next number 2, your brain takes the previous value from your brain which is 1 and add 1 more to it and store it back to 2 in your brain. Same thing when you move your eye to 4. Take the previous value from your brain which is 2 and add +1 which is the final answer (3). Here we lay down our brain as one dimension array. The default value is 1 that mean if you select any number randomly the answer is 1. E.g. [12,4]. If I choose 12 from my eye ball it is 1 or if I choose 4 also the default value is 1. The process of incrementing 1 from previous array value is same as reading the existing brain content and add 1. This is the thumb rule of knapsack problem. You keep updating your brain with the best increasing value by erasing the old content and update the new content. Same here we do select the maximum value of the current value or the previous value +1. Eventually any DP tabulation problem is just converting the eyeball movement calculation into array layout. Hope this helps you. Thank you!!!
There is a small optimization here (Not talking about DP):- Rather than starting j from index 0, start j from i-1 and then go backward. what difference will it make? see below: If let's say you're at index i = 500 Then you move from j=499 and at j=300 you find that its LIS is 200 and array[j] is lesser than array[i], then you make LIS of i=500 as 200+1 = 201. Now when you continue going backward i.e j=299,298,297.......then you do not need to go beyond j=200 because you already know that those elements can have LIS as 200 at max, So no need to compare.... This would save your 200 iterations which you had to do when you were starting j from 0 index.
Additional fact: To backtrack all you need to do is to maintain a separate array of size N, which stores the "j" for which the "i"th index was last updated. Then when you get the maxima in the original array, just search for the index of j recursively, until you reach a number which has the value of 1 in the original array
Maybe I am wrong but can you guys clear me one thing , We call a solution solved through DP when we solved the problem by dividing the main problem and then solving the sub-problem (divide and conquer) and because those sub-problems are overlapping that's why we apply memorization technique to store the overlapping subproblem. The problem here is that if I ask u the LIS for the first 3 index then it should be 2 there but it is stored 1 here , in any dp soln the intermediate values are also the solution of some sub problem This question do contain the memorization technique but I don't think the solution really is a DP.
Great video! I wrote a function in Python that implements the algorithm Tushar exposed in the video. Hopefully this helps someone better understand how it works... def LIS(arr): j, i, t = 0, 1, [1] * len(arr) # initialize ints j, i and array t while i < len(arr): # loop while i is within the sequence's bounds if arr[j] < arr[i]: t[i] = max(t[i], t[j] + 1) # exact same logic Tushar wrote at the end of video j = j + 1 # at each iteration, increment j if j == i: j, i = 0, i + 1 # if j meets i, set j to 0 and increment i return max(t)
bro thx a lot.. most of the youtuber now a days just focus on learning the dp and do recursive solution then convert into dp (tabulation) just follow the prewritten steps by some youtuber.. they don't understand, how amazing the tabulation is..
For people who don't have much time to watch the entire video here is the solution 0:45 --> "Yes we will have to use dynamic programming to solve this "
This is the code from your github public int longestSubsequenceRecursive(int arr[]){ int maxLen = 0; for(int i=0; i < arr.length-1; i++){ int len = longestSubsequenceRecursive(arr,i+1,arr[i]); if(len > maxLen){ maxLen = len; } } return maxLen + 1; } I think, the below code is sufficient. You are unnecessarily looping I think. Please clarify. public int longestSubsequenceRecursive(int arr[]){ return longestSubsequenceRecursive(arr, 0,Integer.MIN_VALUE); }
I have one suggestion. Before solving any DP problem, please first solve it with recursion then only move to DP. This will help us in better understanding of the problem and why is the need of DP here.
at 02:42, why would the value at -1 be 1 ? shouldn't it be 2 ? because the value represents the length of the LIS up until that point. so up until -1, LIS would be of length 2 containing 3 and 4.
It represents the longest increasing subsequence up until that point including the value in question. It's necessary because when you do the comparison later, you need to know the maximum value up to that point. If we set the value at -1 to 2, then a later 0 or 1 would give us a subsequence of 3, which isn't actually true because the full subsequence doesn't contain a -1. For example, if you walk through the algorithm like you described, we would have a longest subsequence value of 3 at value 0, and 4 at value 6.
the index below shows `the LIS about the current number`, instead of `globally longest`, i.e. let's consider the number `6`, we have LIS: 3,4,6, when we check the 3, we add 1 to index of 6, when we check the 4, add 1 again, this process means that `we found at most 3 lengths increasing seq including 6 itself, after we launch this process for all the number, we can find the longest seq by checking the length index
It represents Length of subsequence using elements till that index and *including* that element in the subsequence. So if we include -1 in subsequence, we get {-1} as subsequence.
watched it and tried casually. Here is my working answer. For both of these cases, its working. const arr = [3,4,-1,0,6,2,3] const arr1 = [1, 1, 1, 1, 1,1,1] let j = 0 let i = j + 1 while (j < arr.length) { while (i < arr.length) { if (arr[j] < arr[i]) { // arr1[i]=arr1[j]+1 arr1[i] = Math.max(arr1[j] + 1, arr1[i]) j++ console.log("first", arr1); } else { j++ console.log("second"); } if (j === i) { j = 0 i++ console.log("third"); } } break }
How is this solution any better than a stack based solution ie maintain stack for every element and check for max length? The time would be n^2 space would be n and as a plus point we can even get the elements?
The recursive approach according to me:- 1. Iterate through the array containing the sequence. 2. We will have two options either we can select the first element or not. 3. Now if the next element of the array is greater than the previous element we will again have two choices either we can select the element or not.
Excellent videos!Great going..I haven't seen such wonderful videos with clear explanation.Only through your videos i came to know clearly what dynamic programming actually means. Still that i couldn't understand anything just i thought we need to build a 2D array by your video only i came t know how the principles of dynamic programming are satisfied.Keep posting videos.
I like that you put the word Length at the end of LIS. It is stating that you completely understand it. Finding the length instead of the actual LIS itself was confusing me a lot!
Program in python of this video: t = int(raw_input()) while t!=0: n = int(raw_input()) a = list(map(int,(raw_input()).split(" "))) v = list() for i in range(n): v.append(1) for i in range(1, n): for j in range(0, i): #print j, i, a[j], a[i], v[i], v[j]+1 if a[j]
i have doubt to handle large numbers do we need to learn java or python. since in c and c++ we are unable to solve. we are able to write code but it is unale to process such large data. as i heard only java and python can handle such large data, but c,c++ can't
@Tushar...I went through you code and I finding it hard to understand the 'print the actual solution' part of it wherein you want to print the LIS. Please help.
question: element 6 has count as 3 and last element 3 has count 4 ? ... if element position of j < i then we need to increment count... you have done till element 6 got be 3.. why are you not increasing count at 6 ? where as you increased count for last element 3 even if 4 is not less than 3. am i missing you explanation ? can you please correct me if i m wrong.
Nope... At position i, lis(i) = max ( 1 + lis(i-1) if arr[i] > arr[i-1] 1 + lis(i-2) if arr[i] > arr[i-2] 1 + lis(i-3) if arr[i] > arr[i-3] ... ) For the element 6, lis(4)=max(1+lis(3), 1+lis(2),1+lis(1),1+lis(0))=max(1+2, 1+1, 1+2, 1+1)=3 Hope this helps... :)
Awesome solution! Can you create a video for finding Longest Consecutive Subsequence in unsorted array? e.g Input: arr[] = {1, 9, 3, 10, 4, 20, 2}; Output: 4 The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elements
Its worth to appreciate the hard work. Any one can easily see him so exhausted after doing the daytime job at Apple. But he still makes these helpful videos. Kudos!
Intuition behind this solution:
If the current element is greater than the previous element, we can safely add 1 to the value of previous max sum. Since the previous max sum was also calculated in a similar manner (optimal substructure) we can safely add 1 to previous max value to get the current value.
If you notice in case of 6, since it is greater than 0, you can add 1 to the max value at 0. But there is a catch, you can have previous elements (for example 4) which can give you a bigger subsequence. Hence to check this, every time the "j" begins with zero. Or you can even start at the given i and keep going backwards with a j variable to check if there are two or more contending elements which can give you the max value.
Notice how we construct the solution from using the previous solutions (previous values in array). This is in essence Dynamic Programming where you remember the previous computed values and make calculations faster.
PS: please correct mistakes if any.
This example was so clear and easy to follow that I can only wonder _how_ my professor did such a bad job at explaining this. Thank you!
yes, we will have to use DP to solve this problem. :D:P
XD
staaahpp!!! 😂
Actually a better solution is to use binary search, the time complexity becomes N logN, but its good to know DP
@Tushar: Just a suggestion, it would be great if you can solve it using recursion first and then explain as how this problem falls into DP category.
u are right
I agree that explaining the recursive or iterative brute force method first would be better. Doing so would help with making the connection from how you would solve the problem naively, to how you could use dynamic programming to solve it faster
I dint find one video or good article, explaining recursion solution :(
This is the recursive solution
def li_seq(arr):
if not arr:
return 0
if len(arr) == 1:
return 1
count = 0
for i in range(1,len(arr)):
end_at_i = li_seq(arr[:i])
if arr[-1] > arr[i - 1]:
count = max(end_at_i + 1, count)
return count
he wont do this cuz solving this problem by recursion it would take too much, just imagine that if u give a super long subseqvence it can take up to some months for your computer to find the solution, the best 1
Really really great explanations, thank you very much. Just one suggestion : I thoroughly understood the solution but still I don't know the intuition behind coming up with this solution. Could you please explain that also? Oh And the time complexities as well. thanks again :) :)
The intuition here is like an eye ball movement. Let's say you have a simple array [1,2,4]. The answer is 3. How ? In the eyeball movement you see the number 1 then register in your brain 1 . When you go to the next number 2, your brain takes the previous value from your brain which is 1 and add 1 more to it and store it back to 2 in your brain. Same thing when you move your eye to 4. Take the previous value from your brain which is 2 and add +1 which is the final answer (3). Here we lay down our brain as one dimension array. The default value is 1 that mean if you select any number randomly the answer is 1. E.g. [12,4]. If I choose 12 from my eye ball it is 1 or if I choose 4 also the default value is 1. The process of incrementing 1 from previous array value is same as reading the existing brain content and add 1. This is the thumb rule of knapsack problem. You keep updating your brain with the best increasing value by erasing the old content and update the new content. Same here we do select the maximum value of the current value or the previous value +1. Eventually any DP tabulation problem is just converting the eyeball movement calculation into array layout. Hope this helps you. Thank you!!!
He is such a gem of a person. I don't know why he has stopped making such videos now. Wish he comes back again.
This video is made 6 years ago and still one of the best
Yes..I'm having 3rd semester now😄😨
yea it so crazy. 8 years later, I watched like 10 newer videos yet this is still the best explanation.
Thanks for your sharing ! If only I had seen it earlier 😭！
There is a small optimization here (Not talking about DP):-
Rather than starting j from index 0, start j from i-1 and then go backward. what difference will it make? see below:
If let's say you're at index i = 500 Then you move from j=499 and at j=300 you find that its LIS is 200 and array[j] is lesser than array[i], then you make LIS of i=500 as 200+1 = 201. Now when you continue going backward i.e j=299,298,297.......then you do not need to go beyond j=200 because you already know that those elements can have LIS as 200 at max, So no need to compare.... This would save your 200 iterations which you had to do when you were starting j from 0 index.
Additional fact: To backtrack all you need to do is to maintain a separate array of size N, which stores the "j" for which the "i"th index was last updated. Then when you get the maxima in the original array, just search for the index of j recursively, until you reach a number which has the value of 1 in the original array
this is the O(n^2) solution but in GFG is it mentioned to solve in O(nlogn).
Maybe I am wrong but can you guys clear me one thing ,
We call a solution solved through DP when we solved the problem by dividing the main problem and then solving the sub-problem (divide and conquer) and because those sub-problems are overlapping that's why we apply memorization technique to store the overlapping subproblem.
The problem here is that if I ask u the LIS for the first 3 index then it should be 2 there but it is stored 1 here ,
in any dp soln the intermediate values are also the solution of some sub problem
This question do contain the memorization technique but I don't think the solution really is a DP.
Great video! I wrote a function in Python that implements the algorithm Tushar exposed in the video.
Hopefully this helps someone better understand how it works...
def LIS(arr):
j, i, t = 0, 1, [1] * len(arr) # initialize ints j, i and array t
while i < len(arr): # loop while i is within the sequence's bounds
if arr[j] < arr[i]: t[i] = max(t[i], t[j] + 1) # exact same logic Tushar wrote at the end of video
j = j + 1 # at each iteration, increment j
if j == i: j, i = 0, i + 1 # if j meets i, set j to 0 and increment i
return max(t)
bro thx a lot.. most of the youtuber now a days just focus on learning the dp and do recursive solution then convert into dp (tabulation) just follow the prewritten steps by some youtuber.. they don't understand, how amazing the tabulation is..
After all these years, I still come back to this channel. Always loved the clear way you explain!
For people who don't have much time to watch the entire video here is the solution
0:45 --> "Yes we will have to use dynamic programming to solve this "
This is the code from your github
public int longestSubsequenceRecursive(int arr[]){
int maxLen = 0;
for(int i=0; i < arr.length-1; i++){
int len = longestSubsequenceRecursive(arr,i+1,arr[i]);
if(len > maxLen){
maxLen = len;
}
}
return maxLen + 1;
}
I think, the below code is sufficient. You are unnecessarily looping I think. Please clarify.
public int longestSubsequenceRecursive(int arr[]){
return longestSubsequenceRecursive(arr, 0,Integer.MIN_VALUE);
}
Im out of words, i couldn't find a solution to this problem on my own
#include
using namespace std;
int main(){
int array[]={6,2,5,1,7,4,8,3};
int n=8;
int lenght[8]={1,1,1,1,1,1,1,1};
for(int k=0;k
All your videos are excellent, extremely Helpful.
I have one suggestion. Before solving any DP problem, please first solve it with recursion then only move to DP. This will help us in better understanding of the problem and why is the need of DP here.
Thank you, algoexpert explained it in 1 hour and it was still not clear as yours!! Cheers thnx👍
lmao never buy algorithm courses
just use geeksforgeeks or hackerrank, its wayy better and covers more stuff. Maybe not systems interview stuff but still
For recreation this is a fun video BUT if you wanna look at this from algorithmic point of view this is trash. And please use RECURSION
n(3n)
public static int lengthOfLIS2(int[] nums) {
int[] dp = new int[nums.length];
int max = 0;
int totalJIterations = 0;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
totalJIterations++;
if ((nums[j] < nums[i]) && ((1 + dp[j]) > dp[i])) {
dp[i] = 1 + dp[i];
}
max = Math.max(max, dp[i]);
}
}
// n(3n)
// System.out.println(Arrays.toString(dp));
System.out.println("TotalJIterations: "+ totalJIterations);
System.out.println("Num size: "+ nums.length);
return max + 1;
}
Tushar, you are the shit. Couldn't get through DP w/o you.
+Mike S. he's awesome!
what if the last number in the array is the smallest number? then you would do nothing since arr[i] > arr[j] is false, so the answer just becomes 1?
at 02:42, why would the value at -1 be 1 ? shouldn't it be 2 ? because the value represents the length of the LIS up until that point. so up until -1, LIS would be of length 2 containing 3 and 4.
same question ... Anyone can explain why?
It represents the longest increasing subsequence up until that point including the value in question. It's necessary because when you do the comparison later, you need to know the maximum value up to that point. If we set the value at -1 to 2, then a later 0 or 1 would give us a subsequence of 3, which isn't actually true because the full subsequence doesn't contain a -1. For example, if you walk through the algorithm like you described, we would have a longest subsequence value of 3 at value 0, and 4 at value 6.
the index below shows `the LIS about the current number`, instead of `globally longest`, i.e. let's consider the number `6`, we have LIS: 3,4,6, when we check the 3, we add 1 to index of 6, when we check the 4, add 1 again, this process means that `we found at most 3 lengths increasing seq including 6 itself, after we launch this process for all the number, we can find the longest seq by checking the length index
It represents Length of subsequence using elements till that index and *including* that element in the subsequence.
So if we include -1 in subsequence, we get {-1} as subsequence.
watched it and tried casually. Here is my working answer. For both of these cases, its working.
const arr = [3,4,-1,0,6,2,3]
const arr1 = [1, 1, 1, 1, 1,1,1]
let j = 0
let i = j + 1
while (j < arr.length) {
while (i < arr.length) {
if (arr[j] < arr[i]) {
// arr1[i]=arr1[j]+1
arr1[i] = Math.max(arr1[j] + 1, arr1[i])
j++
console.log("first", arr1);
} else {
j++
console.log("second");
}
if (j === i) {
j = 0
i++
console.log("third");
}
}
break
}
How is this solution any better than a stack based solution ie maintain stack for every element and check for max length? The time would be n^2 space would be n and as a plus point we can even get the elements?
great sir, the way you have explained is awesome, keep it up sir 🙂🙂👍👍👍👍
in 3rd location value is (-1), where u r telling maxLength is 1, but it should be 2. Please verify
Wouldn't your solution be O(n^2)?
It is , he explains a O(n log n) in another video
Could you tell me which video for O(n log n) ? Thanks!
ua-cam.com/video/S9oUiVYEq7E/v-deo.html
yes
Bhai DP laga le ab to ...concept to samajh aa hi gya na
thank you for this video this helped me in my upper div Data Structures class in university for a quiz.
The recursive approach according to me:-
1. Iterate through the array containing the sequence.
2. We will have two options either we can select the first element or not.
3. Now if the next element of the array is greater than the previous element we will again have two choices either we can select the element or not.
no because its not guarenteed that next element itself would contribute to the ans
Excellent explanation ! Thank you for taking the time to make these videos !
Thanks still helpfull
Struggled whole day on a problem on alternating sequence. Then solved within 15 minutes after watching this. Thanks a lot :)
Thanks Brother!!..Very Nice and clear explanation!!
thank you sir
its pretty much finding the number of elements which are less than a certain index...
What if the last element is -3? Then answer would be 1 instead of 4!
Excellent videos!Great going..I haven't seen such wonderful videos with clear explanation.Only through your videos i came to know clearly what dynamic programming actually means. Still that i couldn't understand anything just i thought we need to build a 2D array by your video only i came t know how the principles of dynamic programming are satisfied.Keep posting videos.
definition of subsequence is confusing - leetcode.com/problems/longest-continuous-increasing-subsequence/
굿 깔끔한 설명
Theres a bug in the code, it doesnt pass a particular test case in leetcode.
[1,6,4,2,7,5,34,8,6,34,45,7,4,2,75,3,55,7657,6547,345,3254,12364,4435,4]
expected is 10, but it returned 9
@@irvinge4641 No its giving 10
What it is the best, worst and average case?
seems like this is O(n^2) complexity, isn't this costly, aren't there any better solutions ?
You can use binary search for optimized this problem;
int d[MAXN];
d[0] = -INF;
for (int i=1; i
how can u use binary search when the data is not sorted? can u provide a full working code?
ideone.com/5L3zHE
O(nm) not O(n^2)
I like that you put the word Length at the end of LIS. It is stating that you completely understand it. Finding the length instead of the actual LIS itself was confusing me a lot!
after finding the length, how do we get the elements in the sequence?
what shall be done to extract the sequence of max length ?
Why is the answer 1 for subproblem 2 (with subarray [3,4,-1])? I would have thought 2, since {3,4} can be formed....
how easily you explain complex things in a snap.
*Best & shortest implementation in CPP using std*
int lengthOfLIS(vector& a)
{
int i,ind,n=a.size();
vector v;
v.push_back(a[0]);
for(i=1;iv.back()) v.push_back(a[i]);
else
{
ind=lower_bound(v.begin(),v.end(),a[i])-v.begin();
v[ind]=a[i];
}
}
return v.size();
Nicely Explained. Like it very much. In any of your videos, is it explained with O(N Logn N) complexity?
No fancy animation, no BS music and intros, 100% explanation, You make it look like it's a piece of cake.
Program in python of this video:
t = int(raw_input())
while t!=0:
n = int(raw_input())
a = list(map(int,(raw_input()).split(" ")))
v = list()
for i in range(n):
v.append(1)
for i in range(1, n):
for j in range(0, i):
#print j, i, a[j], a[i], v[i], v[j]+1
if a[j]
trying to solve for last 30 min, but couldn't do it. And after seeing such simple explanation i am totally broken.
The of explaining is owsm ❤️
i have doubt to handle large numbers do we need to learn java or python.
since in c and c++ we are unable to solve.
we are able to write code but it is unale to process such large data.
as i heard only java and python can handle such large data, but c,c++ can't
1000000, if input is this long will it not give "terminated due to run out" message in java.
Thanking you very much
Wow, that’s the first video on that subject there I finally understand the algorithm! Many thanks!:)
Nice, but is it possible to get the subsequence also ?? Since you gave that option in "Longest Common Subsequence" video :)
great video, thank you!
What is the time comoplexity of this algorithm?
@Tushar...I went through you code and I finding it hard to understand the 'print the actual solution' part of it wherein you want to print the LIS. Please help.
nlgn solution : ua-cam.com/video/Rf0Mod_uQKw/v-deo.html
There is O(nlogn) way to get LIS. can u explian that one or provide links for the solution ?
This video is the definition of precise.
@Tushar You are awesome man , dp was a real pain for me, after seeing your videos, I am so comfortable, keep up the great work!!!!
Awesome explanation!
Far better than the one of GeeksForGeeks
Thank you so much for making these helpful videos!! I watched this whole playlist before my dynamic programming exam and I got an A on it.
What is time complexity of this program
Hello Tushar, can you also explain the surpasser count problem.
when i is at 6 its value gets increased to 2 because of 3 &4 then after that 0 & -1 is also less than 6 ,then why the value is not increased?
The value of 0 and -1 is less than the value when i is 6,so this is not increased
2022_06_24, I learned and implemented this good algorithm. Thank you!
Program is failing for larger input. Example 1000 numbers. Namely it was getting timed out
How to print the subsequence itself?
very nice solution, thanks!
explanation couldnt get any better.
I think this lecture could be better if the lecturer had talked about analysis of time achieved by the suggested algorithm.
What happens if you start with -1 at starting then value of j would never going to inc.
y so serious dude?
Dude you just killed it !! Awesome explanation !!
can u elaborate if this can be done using matrix option, instead of memization, as u have done most of ur videos
Thank you so much for making this video easy to understand. Keep going on!
question: element 6 has count as 3 and last element 3 has count 4 ? ... if element position of j < i then we need to increment count... you have done till element 6 got be 3.. why are you not increasing count at 6 ? where as you increased count for last element 3 even if 4 is not less than 3. am i missing you explanation ?
can you please correct me if i m wrong.
Nope...
At position i,
lis(i) = max (
1 + lis(i-1) if arr[i] > arr[i-1]
1 + lis(i-2) if arr[i] > arr[i-2]
1 + lis(i-3) if arr[i] > arr[i-3]
...
)
For the element 6, lis(4)=max(1+lis(3), 1+lis(2),1+lis(1),1+lis(0))=max(1+2, 1+1, 1+2, 1+1)=3
Hope this helps... :)
Awesome solution! Can you create a video for finding Longest Consecutive Subsequence in unsorted array? e.g
Input: arr[] = {1, 9, 3, 10, 4, 20, 2};
Output: 4
The subsequence 1, 3, 4, 2 is the longest subsequence
of consecutive elements
But they r not in sequential order. I have a doubt in it? Will u pls sort it out?
I stugled to understand this problem and referred other sources as well. This video gave me a final push to clear my understanding. Thanks Tushar!
can we do better than O(n2) ?
Write a program to find the longest progressive sequence arranged in ascending order in c
this vid is 7 years old damnnnn
Brilliant. Love you man.
thank you so much Tushar Sir
You are a legend.
first time I found best video of LIS question.
thanks from bottom of my heart!
he seems a bit sad in the start
Time Complexity? O(n)? where n is length of array?
Can anyone send me link ,I am not able to open it
github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestIncreasingSubsequence.java
If you're not able to open it then use VPN.
Nice explanation, subscribed after watching first video of this channel, thanks