The Longest Increasing Sub-sequence problem is to find a sub-sequence of a given sequence in which the sub-sequence's elements are in sorted order, lowest to highest, and in which the sub-sequence is as long as possible. This sub-sequence is not necessarily contiguous, or unique. Longest increasing sub-sequences are studied in the context of various disciplines related to mathematics, including algorithms, random matrix theory, representation theory, and physics.
Like example :
Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing sub-sequence is {3, 7, 40, 80}
Here for our input Array, we will divide our main problem into smaller sub-problems, like we will create a new array named(dp[]), in which we will pre-compute longest increasing sub-sequence up-to index 'i' in dp[i].
Lets see the code, follow the comments :)With the help of dp[] array, we get every longest increasing sub-sequence up-to every particular index 'i'.
Here 'best_ans' will be the maximum element of our dp array.
As first 'For' loop will run upto 'n' and whole nested 'For' loop will run for
1 + 2 + 3 .......n values
which will be n*(n+1)/2 i.e
1 + 2 + 3 .......n values
which will be n*(n+1)/2 i.e
Time Complexity of the above code will be O(n^2)
We can improve this by removing the inner loop and executing " Binary Search ( Complexity of BS : O(log n) ),
so overall complexity will be O(n*log n). While implementing this logic, this time, dp[i] will be the element at which a sequence of length 'i' terminates. Following is the implementation in code:
so overall complexity will be O(n*log n). While implementing this logic, this time, dp[i] will be the element at which a sequence of length 'i' terminates. Following is the implementation in code:
:)
Our 'Main' Function :
Thanks for reading, for further references, PFA this useful link :
Longest increasing subsequece
Problems related to LIS :
Problems related to LIS :
Comments
Post a Comment