Buy and Sell stock twice

Buy and Sell stock twice 

Problem Statement 

Given an array of stock prices on each day. Write a program that gives the maximum profit one can achieve by buying and selling a stock at most twice. 

Problem Solving

• Immediately I started to think like I solved the previous one stock problem and thought of instead of registering one max_profit I can register two maxprofits. 
• However this could make the complexity n*m where m is the number of times we can sell. 
• For eg. We would iterate the array looking for local minima and keep updating the max_profit array[2]. However we need to make sure that we evict the smallest of the profits. For 2 this could simple be a std::pair with wrapper. However for n elements we need to make a priority queue (earlier I thought of linklist which can cause quadratic runtime) which can make the eviction and insertion log n. That would make the total complexity be O(nlogm) 
• However as I saw in the book there is an linear order time complexity solution to this problem. 
• So I cheated and looked at the answer. I took me some time to understand and that's because If I would have spent some time thinking about how to optimize this solution to O(n) probably I would have fired my neurons which already know this technique because I remember I used this technique to solve the Google Interview question. That means somewhere in my brain this chain of thought is present it's only to reach that thought with reasoning. 
• So after writing about how guilty I feel, let move to the answer. 
• What we can do here is to understand that we need to make utmost 2 buy sell and strictly one after an other. 
• This one after an other also is a good hint for this technique. 
• So what we can do is that we iterate and store results from left to right and from right to left registering max_profit one could make only considering 0...i values and in the reverse array we would have max_profit from i+1 ... n. 
• Finally to get the answer we iterate both the arrays and get max of sum of both arrays and that  would be our answer. 
• One optimization that they have done here it that instead of doing the operation of calculating reverse and then adding they have clubbed the last two steps in the same array to save space and time. Smart ! 
• Find code here.

Learnings

• Do not jump to answers please. 
• This would not register in the brain properly if I haven't reasoned about it well and just looked at the answer. 
• The technique is good and easily understandable. 
• My original solution however is scalable. We can make it to calculate n sell and buy opportunities.  
• One good thing that happened was that once the algo was in my head I coded and it worked in first time without having to redo any algo changes. So that is a good sign.