I've been trying to solve a variation of this problem https://stackoverflow.com/questions/62389658/best-time-to-buy-and-sell-stocks-when-allowing-consecutive-buys-or-sells
You are given an input array of non-negative integers. You are allowed to either buy 1 share or sell any number of shares that you own, or not make any transaction in each time period. Find the maximum profit you can obtain.
Purchases are negative and sales are positive cash flows. For example, if prices are [3,4,5,3,5,2] the maximum profit can be realized by purchasing a share in each of the first two periods for cash flows -3 + -4 = -7 then selling them both at the 3rd period for 2*5 = 10.
Alternatively, you may purchase a share in 4th period for 3 and sell in 5th period for 5. Total profits are – 3 -4 + 10 -3 + 5 = 5. Another way to the same outcome is to purchase shares in each of 1,2,4th periods for -3 -4 -3 = -10 do nothing at the 2nd period then sell all 3 shares at the 5th period (total 3*5 = 15) for a total profit -10 + 15 = 5.
I've attempted several dynamic programming approaches, but the closest to the solution I found was min-cost flow approach in the link I provided. However, its a slightly different variation as here you are allowed to sell all your shares on a given day.
Its been mentioned in the comments a dynamic programming approach may work, however I cannot find a recursive relationship to even start on the problem. Any hints would be appreciated.