45. DP on stocks

these are just knapsack variations
---------------------------------------------------------------------------------------------------------------
DP on stocks-1:
(1 transaction)
Ques- we want to find max profit we can make by buying on i-th day and selling of a day > i

Soln- iterating from start to end , see profit for each guy as curr - min(from start to prev index )

-----------------------------------------------------------------------------------------------------------------------------
DP on stocks-2:
(Infinite transactions)
e.g., 715364:  (1-5, 3-6) => (4+3=7)

Approach-1: greedy

Approach-2: DP
return dp[0][1]
---------------------------------------------------------------------------------------------------------------
DP on stocks-3:
(max 2 transactions)


--------------------------------------------------------------------------------------------------------------
DP on stocks-4:
(max K transactions)

simple- upar wale code mein 2 ki jagah k daaldo
---------------------------------------------------------------------------------------------------------------
DP on stocks-5:
(cooldown of 1 day after a sell- BScBScBS... & infinite transactions)

simple- infinite transactions ke code mein sell krne wali condition mein i+1 ki jagah i+2 krde

PS- yaha space optimisation mein prev1 aur prev2 lagenge aur tabulation mein n+2 tak krna padega
---------------------------------------------------------------------------------------------------------------
DP on stocks-6:
(with transaction fee + infinite transactions) 

simple: sell wale mein agar sell kar rhe ho toh ( - fee ) bhi kardo
--------------------------------------------------------------------------------------------------------------

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