maximizing profit for given stock data via DP

问题:

You are given the stock prices for a set of days . Each day, you can either buy one unit of stock, sell any number of stock units you have already bought, or do nothing. What is the maximum profit you can obtain by planning your trading strategy optimally?

Now the answer can be obtained through single pass but what if it has to be solved through Dynamic Programming. What will be the recurrence relation then for the problem?

I think for any day OPT(i) can denote maximum profit earned so far, so one has to sell all remaining shares on the last day so

OPT(i) = max (
         Sell all on this day bought from day j to day i + OPT(j-1), 
         OPT(i-1) + do nothing)?

Is this right?

回答1:

I think you can solve like this:

dp[i][j] means the maximum profit you get while you are still holding j units of stock.

Then

dp[i][j] = max(dp[i-1][j-1] - cost, //buy one unit
               dp[i-1][j], // do nothing
               dp[i-1][j+1] + profit // sold one unit
               dp[i-1][j+2] + 2*profit //sold two units
               ...
               )

then find the maximum value of dp[N][j] (0<=j<=MAX)

The time is (number_of_days * total_stock_you_can_buy^2)