Sell stocks and understand DP & Greedy

Like Father is to Son , Recursion is to DP — Ayush Singh

Problem statement :-

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Sample I/p, O/p :-

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Approach :-

Recursive :-

1. Suppose I pick some in-between input element say ‘i’. Now I have to first verify whether I am in a position to buy or sell. So for this we can use a variable/state ‘buy’.
2. When buy ==0 , I can buy or not buy, else I can sell/not sell.
3. Every time I decide to buy(i.e subtract) or sell(i.e add), I am affecting my profit. The task here is to have maximum profit. So every time a make a choice to buy/not buy, sell/ not sell , I only pick the max of my choices result(i.e return value).

Recursive approach

Taste of DP :)

From the diag, lets further visualize :-

[1,5,3,6,4]||buy=0 => lets make a choice of buy now, Therefore our new updated states will be [5,3,6,4]||buy=1 .

Now have a look in the diag, is there any similar combination state?? Yes, its there. And we would have already solved it right. Then it is better if we store the result of that combination state and use it next time.

That’s it , DP is achieved. You just optimized your code.

DP soln to the problem(memoized soln)

Bottom-up

If you prefer a bottom-top approach :- we have to start from the leaf and reach root.

iterative approach

code :-

Iterative approach code

Now that we have solved iteratively and formed a proper reasonable table. We can think about reducing space and complexities (e.g :- if we know just previous value , we can reach ans). Therefore we can optimize memory also now.

Thinking Greedy :-

Note :- It isn’t always that greedy condition satisfies, but it is always good to try it out for all those max/min kind of problems.

If we look at the problem from statistical point of view :-

incrementation from lowest to highest is where profit is made

Also, the fact :-

Logic :- The distance between points is always same, so it doesn’t matter whether you do (1000–1) or (50–1)+(100–50)+(1000–100)

So, it is enough if we calculate every single hike from low to high :-

for every single hike, we get profit

That’s how it is done :)

Smart work pays off!!!

TRY OUT THIS PROBLEM Yourself !!!!