i have a very short solution: i read about it somewhere on CF blog #include using namespace std; int main() { int n; cin >> n; vector dp; for (int i = 0; i < n; i++) { int x; cin >> x; auto it=lower_bound(dp.begin(),dp.end(),x); if(it==dp.end()){ dp.push_back(x); }else{ *it=x; } } cout
great explanation i had solved using recursion and memo that was quite intuitive ...i was struggling with tabular and binary approach ..i skipped this video earlier as it as low views ..boy i was wrong ....
If instead of using DP we just sorted the array and then looped to check if next element is current element+1, wouldn't that work too? Time complexity will also be O(nlogn).
Naive C/C++ recursive implementation of LIS problem */ #include #include /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ int _lis( int arr[], int n, int *max_ref) { /* Base case */ if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall // max. And update the overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis( arr, n, &max ); // returns max return max; } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr)/sizeof(arr[0]); printf("Length of lis is %dn", lis( arr, n )); return 0; } Output: Length of lis is 5 Complexity Analysis: Time Complexity: The time complexity of this recursive approach is exponential as there is a case of overlapping subproblems as explained in the recursive tree diagram above. Auxiliary Space: O(1). No external space used for storing values apart from the internal stack space. Method 2: Dynamic Programming. We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation. The simulation of approach will make things clear: Input : arr[] = {3, 10, 2, 11} LIS[] = {1, 1, 1, 1} (initially) Iteration-wise simulation : arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2} arr[3] < arr[1] {No change} arr[3] < arr[2] {No change} arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2} arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3} arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3} We can avoid recomputation of subproblems by using tabulation as shown in the below code: Below is the implementation of the above approach: /* Dynamic Programming C++ implementation of LIS problem */ #include using namespace std; /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ int lis( int arr[], int n ) { int lis[n]; lis[0] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = 1; i < n; i++ ) { lis[i] = 1; for (int j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; } // Return maximum value in lis[] return *max_element(lis, lis+n); } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr)/sizeof(arr[0]); printf("Length of lis is %d ", lis( arr, n ) ); return 0; }
I like the explanation. I, however, think that the solution [2, 5, 6, 8] is not correct. It breaks the subsequence definition. It should be [3, 5, 6, 8]. en.wikipedia.org/wiki/Subsequence
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
You explained it better than those channels with 100k+ subs.
Thanks mate!
BEST EXPLANATION UP THERE ON INTERNET...THANK YOU, SIR
You're really underrated and have helped me a lot. Please keep up the great videos!
Very good lecture..The concept is explained beautifully..Thank you sir..I appreciate your work sir...Keep going....
i have a very short solution: i read about it somewhere on CF blog
#include
using namespace std;
int main() {
int n;
cin >> n;
vector dp;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
auto it=lower_bound(dp.begin(),dp.end(),x);
if(it==dp.end()){
dp.push_back(x);
}else{
*it=x;
}
}
cout
great explanation bro
i was struggling to understand it
Thanks for the explanation sir.....you are doing a great job
Thanks Parag :)
one of the best explanation of this problem Thank you sir
great explanation i had solved using recursion and memo that was quite intuitive ...i was struggling with tabular and binary approach ..i skipped this video earlier as it as low views ..boy i was wrong ....
Oh so u choose videos based on the no. of views ? Lol
@@sriramkrishnamurthy4473 no google does ..more views and like make you on top of search
Crystal clear explanation 👏
great explanation!! your explanation make implementation very easy!!
Nice video ... explaining everything in deep.
The best explanation ever!
excellent explanation sir, thanks a lot.
Awesome Explanation
Wonderfully explained
i did this problem using segment tree
which software you use to write on screen , does it works with touch pad on laptop ?
Epic pen
@@aayushvrshney epic pen for software
HUION drawing tablet as hardware
Please discuss CSES tree problems
I will hopefully add two more problems from that section by tonight/tomorrow.
Can you please share editorial link to CSES problems ( if there is any )
, I am not able to find it anywhere on net ?
the codeforces has editiorials of the cses problemsets.
thank you
Demn!
If instead of using DP we just sorted the array and then looped to check if next element is current element+1, wouldn't that work too? Time complexity will also be O(nlogn).
Sorting will change the order of elements
@@himanshujain9082 exactly
@@mihirkumarsrivastava1895 exactly
@@anshumandas5392 exactly
Naive C/C++ recursive implementation
of LIS problem */
#include
#include
/* To make use of recursive calls, this
function must return two things:
1) Length of LIS ending with element arr[n-1].
We use max_ending_here for this purpose
2) Overall maximum as the LIS may end with
an element before arr[n-1] max_ref is
used this purpose.
The value of LIS of full array of size n
is stored in *max_ref which is our final result
*/
int _lis( int arr[], int n, int *max_ref)
{
/* Base case */
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS
// ending with arr[n-1]
int res, max_ending_here = 1;
/* Recursively get all LIS ending with arr[0],
arr[1] ... arr[n-2]. If arr[i-1] is smaller
than arr[n-1], and max ending with arr[n-1]
needs to be updated, then update it */
for (int i = 1; i < n; i++)
{
res = _lis(arr, i, max_ref);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall
// max. And update the overall max if needed
if (*max_ref < max_ending_here)
*max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
int lis(int arr[], int n)
{
// The max variable holds the result
int max = 1;
// The function _lis() stores its result in max
_lis( arr, n, &max );
// returns max
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of lis is %dn",
lis( arr, n ));
return 0;
}
Output:
Length of lis is 5
Complexity Analysis:
Time Complexity: The time complexity of this recursive approach is exponential as there is a case of overlapping subproblems as explained in the recursive tree diagram above.
Auxiliary Space: O(1). No external space used for storing values apart from the internal stack space.
Method 2: Dynamic Programming.
We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
The simulation of approach will make things clear:
Input : arr[] = {3, 10, 2, 11}
LIS[] = {1, 1, 1, 1} (initially)
Iteration-wise simulation :
arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
arr[3] < arr[1] {No change}
arr[3] < arr[2] {No change}
arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}
We can avoid recomputation of subproblems by using tabulation as shown in the below code:
Below is the implementation of the above approach:
/* Dynamic Programming C++ implementation
of LIS problem */
#include
using namespace std;
/* lis() returns the length of the longest
increasing subsequence in arr[] of size n */
int lis( int arr[], int n )
{
int lis[n];
lis[0] = 1;
/* Compute optimized LIS values in
bottom up manner */
for (int i = 1; i < n; i++ )
{
lis[i] = 1;
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
// Return maximum value in lis[]
return *max_element(lis, lis+n);
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of lis is %d
", lis( arr, n ) );
return 0;
}
in trying to be precise you are overtly complicating stuff, try to keep it simple
I like the explanation. I, however, think that the solution [2, 5, 6, 8] is not correct. It breaks the subsequence definition. It should be [3, 5, 6, 8]. en.wikipedia.org/wiki/Subsequence