SDE - Intern

First, think about what we can do on day i? You either have one stock or you don't on day i. For each case, you have two options, making a total of four possible actions on day i:

you have 1 stock and you sell it
you have 1 stock and you do nothing
you have 0 stock and you buy stock i
you have 0 stock and you do nothing
As you can imagine, these four actions are correlated between day i-1 and day i. For example, if you take action 1 on day i, you then have either taken action 2 or 3 on day i-1 but not 1 or 4. In precise, two consecutive days are related as follows:

if you take action 1 on day i ==> you have either taken action 2 or 3 on day i-1
if you take action 2 on day i ==> you have either taken action 2 or 3 on day i-1
if you take action 3 on day i ==> you must have taken action 4 on day i-1 (you can not sell on day i-1 due to cool down)
if you take action 4 on day i ==> you have either taken action 1 or 4 on day i-1
Now you want to maximize your total profit, but you don't know what action to take on day i such that you get the total maximum profit, so you try all 4 actions on every day. Suppose you take action 1 on day i, since there are two possible actions on day i-1, namely actions 2 and 3, you would definitely choose the one that makes your profit on day i more. Same thing for actions 2 and 4. So we now have an iterative algorithm.

Before coding, one detail to emphasize is that the initial value on day 0 is important. You basically cannot take action 1, so the corresponding profits should be 0. You cannot take action 2 in practice, but you cannot set up the profit to 0, because that means you don't have a stock to sell on day 1. Therefore, the initial profit should be negative value of the first stock. You can also think of it as you buy the stock on day -1 and do nothing on day 0.

Initialize two sets, s1 & s2 to store the integers.
Iterate over the range [1, N+1] and store every integer in s1.
Similarly, iterate over the range [1, M + 1] and store every integer in s2.
Traverse the array H[] and remove all H[i] from s1.
Similarly, traverse the array V[] and remove all V[i] from s2.
Convert updated s1 and s2 sets into lists l1 and l2.
Sort both the lists in ascending order.
Traverse the list l1 and l2 and store the maximum distance between two neighbours as maxH and maxV respectively.
Print the product of maxH and maxV as the largest area.

Create an auxiliary stack, say ‘trackStack’ to keep the track of maximum element
Push the first element to both mainStack and the trackStack. 
Now from the second element, push the element to the main stack. Compare the element with the top element of the track stack, if the current element is greater than the top of trackStack then push the current element to trackStack otherwise push the top element of trackStack again into it. 
If we pop an element from the main stack, then pop an element from the trackStack as well. 
Now to compute the maximum of the main stack at any point, we can simply print the top element of Track stack.

Create an array max_upto and a stack to store indices. Push 0 in the stack.
Run a loop from index 1 to index n-1.
Pop all the indices from the stack, which elements (array[s.top()]) is less than the current element and update max_upto[s.top()] = i – 1 and then insert i in the stack.
Pop all the indices from the stack and assign max_upto[s.top()] = n – 1.
Create a variable j = 0
Run a loop from 0 to n – k, loop counter is i
Run a nested loop until j < i or max_upto[j] < i + k – 1, increment j in every iteration.
Print the jth array element.

when rotating the array, there must be one half of the array that is still in sorted order.
For example, 6 7 1 2 3 4 5, the order is disrupted from the point between 7 and 1. So when doing binary search, we can make a judgement that which part is ordered and whether the target is in that range, if yes, continue the search in that half, if not continue in the other half.

Used Memoization.
since we are finding s2 subsequences in s1. So at any point of execution, if s1.length() becomes lesser then s2.length()