46. DP on LIS

 1. find LIS length-

Approach-1: Recursion + memoization

simple- pick, notpick, mein bas pick ek condition mein hoga is baar
f (idx, prevIdx) means LIS of array starting from i=idx with prev=num[prevIdx]
we have to do coordinate shift by +1 of prevIdx, as we can't access -1 prevIdx in dp table, means we will store things like -1 wali at 0 and so on...

---------------------------------------------------------------
Approach-2: tabulation:

------------------------------------------------------------
Approach-3: non intuitive (used widely in variants of LIS)

here, dp[i] means LIS that ends at index i

if we are at index j, then we will check elements with index  < j , such that they are 
< nums[j] , if so, then possible LIS of these will be max ( (LIS at such i's ) + 1 ) = LIS(j)
-----------------------------------------------------

Approach-4: using LCS + sorting

create a sorted vector containing only uniques(since LIS is strictly increasing) from given vector & take LCS of both vectors

---------------------------------------------------------

Approach-5: using binary search (nlogn time here, upar sabme n^2 tha)

                           

we will reuse same subsequence

--------------------------------------------------------------------------------------------------------------

2. print LIS-⭐

use approach 3 along with an array storing index of previous element which updated current element's  LIS

------------------------------------------------------------------------------------------------------------
                                    3. Largest divisible subset-

unlike subsequence, in a subset, we can pick elements in any order
Variant of LIS approach 3

recursive approach-


LIS variation with a divisibility check condition-

sort the given vector & ques becomes Longest divisible subsequence

--------------------------------------------------------------------------------------------------------------
4. length of Longest string chain⭐

imp helper function
- similar to LIS , just that instead of increasing subsequence we have to check if difference between 2 adjacent words is of exactly 1 different character
- the words can be compared using 2 pointer 
- we will sort the given vector of strings according to length before doing LIS, since in ques it is asked for sequence/ subset instead of subsequence
-----------------------------------------------------------------------------------------------------------

5. Longest bitonic subseq

LIS + LDS
bitonic means subseq is first strictly increasing then strictly decreasing
---------------------------------------------------------------------------------------------------------------

6. Count LIS⭐

we have to actually count no. of ways by which we can have LIS on max length from given array,
- so we will use a count vector & do as follows in n2 approach of LIS-
- if( lis[j] == lis[i] )    cnt[i] += cnt[j]
- lis[i] = max ( lis[i] , lis[j] +1 )
--------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more