Can you please explain me what we are trying to find in this particular topic because I am having trouble understanding it? Please explain with example!
Longest Increasing subsequence
hello @div_yanshu07
In this problem we will be given an array and we need to find subsequence( a subset of given array ) such that they satisfy following constraints.
a) elements in that sequence should be increasing order
b) the length of that subset should be maximum
for example->
Input: arr[] = {3, 10, 2, 1, 20}
Output: Length of LIS = 3
The longest increasing subsequence is 3, 10, 20 (note elements are in increasing order and the size (3 ) is maximum )
So, we have to pick elements from left to right so that it makes subarray of longest length. Right?
subarray is incorrect word( subarray means that the picked elements are present at consecutive indices in original array).
use word subsequence (ie we can pick any elements from array need not to be consecutive )
note : picking order should be from left to right only , u cannot pick in random order
1 Like