通过DP获得给定股票数据的利润最大化 [英] 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?

我认为在任何一天 OPT（i）都可以表示到目前为止赚取的最大利润，因此必须在最后一天卖出所有剩余的股票，因此

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)?

这对吗？

推荐答案

我认为您可以这样解决：

I think you can solve like this:

dp [i] [j]表示当您仍然持有j时获得的最大利润

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

然后

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
               ...
               )

然后找到dp [N] [j]的最大值（0 <== j <= MAX）

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

时间为（天数* total_stock_you_can_buy ^ 2）

The time is (number_of_days * total_stock_you_can_buy^2)

这篇关于通过DP获得给定股票数据的利润最大化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！