0
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ "the link I provided" - I don't see a link $\endgroup$
    – D.W. ♦
    Jul 26 at 22:47
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W. ♦
    Jul 26 at 22:47
  • $\begingroup$ It seems you copied from your post on SO (stackoverflow.com/q/76774147/781723) without copying over the link. Also, I don't see that this has addressed the feedback that you got there (stackoverflow.com/questions/76774147/…). See the link I provided for how to make a systematic attempt at finding a dynamic programming algorithm. Please edit your post to address each of these points. $\endgroup$
    – D.W. ♦
    Jul 26 at 22:48
  • $\begingroup$ I've added the link- hyperlink didn't copy over. I've also deleted the duplicate question in SO. I've tried dynamic programming but it doesn't work. I cannot find a recursive relation. $\endgroup$
    – TWhite
    Jul 27 at 6:52
  • $\begingroup$ Please edit the question to provide a self-contained statement of the problem, in a way that can be understood without having to refer to a separate link. What are the inputs to the algorithm? What are the limits on acceptable solutions? Are there multiple stock companies that can be bought/sold? Is there an initial cash balance, and the cash on hand can never go negative? etc. $\endgroup$
    – D.W. ♦
    Jul 27 at 7:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.