给定的股票报价最大化利润
在面试时我被问到了这个问题，并在最近的比赛中再次看到了这一点
代码冲刺：系统
**问题：
给你一个天的股票价格。 你可以每天购买一单位的股票，出售任何你已经购买的股票单位，或者什么也不做。 通过最佳地规划您的交易策略，您可以获得的最大利润是多less？
示例（input即date的不同可能会有所不同）
5 3 2 =>利润= 0 //由于价格每天都在下降，我们可以赚取的最大利润= 0
1 2 100 =>利润= 197
1 3 1 2 =>利润= 3 //我们以3的价格买入1，然后我们以1买入，卖出2 ..总利润= 3
我的解决scheme
a）find股票价格最大的那一天。 继续购买1单位的股票，直到那一天。
b）如果那一天是最后一天，那么退出：
否则：当天卖出所有的股票，并在那一天之后拆分数组，然后recursion剩余的元素
c）合并利润
例如1 4 1 2 3
a）第2天股价最高..所以我们在第1天买入股票并在第2天卖出（利润= 3），然后我们在剩下的日子里递减：1 2 3
b）最大价格是3（第5天），所以我们在第3天和第4天持续购买股票，在第5天卖出（利润=（3 * 2-3）= 3）
c）总利润= 3 + 3 = 6
这个复杂性原来是O（n ^ 2）。 这个解决scheme通过了11个案例中的10个，但超过了最后一个testing案例的时间限制（即最大的input）
所以我的问题是任何人都可以想到一个更有效的解决这个问题？ 有dynamic编程解决scheme吗？
PS：这是我第一次在这里问一个问题。 所以请让我知道如果我需要改善/添加这个问题的东西
我同意你的方法的逻辑，但不需要做recursion处理或全局最大值search。 要find卖/买天，你只需要每天看一次：
诀窍是从头开始。 如果您的旅行时间倒退，股票交易很容易！
如果你认为代码比文字更容易阅读，可以跳过我的解释，但这里是：
从最后看，看当天的价格。 这是迄今为止最高的价格（从最后），然后出售！ 最后一天（我们开始阅读的时候）你总是会卖出去的。
然后去第二天（记住，时间倒退）。 是迄今为止最高的价格（从我们所看到的所有）？ – 然后卖掉，你不会find更好的一天。 否则价格会上涨，所以买。 继续以同样的方式，直到开始。
整个问题是通过一个单一的反向循环来解决的：计算交易的决策和利润。
下面是类似Python的代码：（我避免了大多数pythonic的东西，应该是C人可读的）
def calcprofit(stockvalues): dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell prof=0 m=0 for i in reversed(range(len(stockvalues))): ai=stockvalues[i] # shorthand name if m<=ai: dobuy[i]=0 m=ai prof+=m-ai return (prof,dobuy) 例子：
calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0]) calcprofit([1,2,100]) gives (197, [1, 1, 0]) calcprofit([5,3,2]) gives (0, [0, 0, 0]) calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives (798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0])
请注意， m是我们所看到的最高股价（从最后）。 如果ai==m那么步骤中购买的股票的利润为0：那个点之后我们有降价或者稳定的价格，并且没有买入。
您可以通过一个简单的循环来validation利润计算是正确的（为了简单起见，想象一下它在上述函数内）
stock=0 money=0 for i in range(len(stockvalues)): if dobuy[i]: stock+=1 money-=stockvalues[i] else: money+=stockvalues[i]*stock stock=0 print("profit was: ",money)
另一种看待它的方法是：
在预处理中，对于每个元素a[i]finda[j] st j > i并且它最大化(a[j] - a[i])
所以，你可以做一个价格在a[i]是在a[i]购买和出售在a[j] 。 如果不存在a[j] a[j] > a[i]那么a[i]根本不是买入点。
预处理时间： O(N)
S[N-1] = A[N-1]; for(int i=N-2; i>=0; --i) S[i] = max(A[i], S[i+1]);
在这里，S [i]是你应该出售[i]的价格。
总结总利润： O(N)
long long int Profit = 0; for(int i=0;i<N;++i) Profit += max(0, (S[i]-A[i]) );
对于这个任务的另一个O（n）解决scheme可以通过使用局部最小值和最大值来find最大值和最小值之间的最佳偏差（利润），因为知道最大值应该具有更大的索引，然后最小值。 我们还需要查看以前最好的本地分钟（C＃实现）。
public int[] GetBestShareBuyingStrategy(int[] price) { var n = price.Length; if (n <= 1) return null; var profit = 0; var min = 0; var max = 0; var lmin = 0; for (var i = 1; i < n; i++) { var lmax = i; var lp = price[lmax] - price[lmin]; if (lp <= 0) { lmin = i; } else { var tp = price[lmax] - price[min]; if (lp > tp && lp > profit) { min = lmin; max = lmax; profit = lp; } else if (tp > profit) { max = lmax; profit = tp; } } } return profit > 0 ? new [] {min, max} : null; } [Test] [TestCase(new[] { 10, 9, 8, 7, 3 })] [TestCase(new[] { 5, 5, 5, 5, 5 })] [TestCase(new[] { 5, 4, 4, 4 })] [TestCase(new[] { 5, 5, 3, 3 })] public void GetBestShareBuyingStrategy_When_no_sense_to_buy(int[] sharePrices) { var resultStrategy = GetBestShareBuyingStrategy(sharePrices); Assert.IsNull(resultStrategy); } [Test] [TestCase(new[] { 10, 8, 12, 20, 10 }, 1, 3)] [TestCase(new[] { 5, 8, 12, 20, 30 }, 0, 4)] [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)] [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)] [TestCase(new[] { 10, 2, 8, 1, 15, 20, 10, 22 }, 3, 7)] [TestCase(new[] { 1, 5, 2, 7, 3, 9, 8, 7 }, 0, 5)] [TestCase(new[] { 3, 5, 2, 7, 3, 9, 8, 7 }, 2, 5)] public void GetBestShareBuyingStrategy_PositiveStrategy(int[] sharePrices, int buyOn, int sellOn) { var resultStrategy = GetBestShareBuyingStrategy(sharePrices); Assert.AreEqual(buyOn, resultStrategy[0]); Assert.AreEqual(sellOn, resultStrategy[1]); }
我刚刚在比赛现场解决了这个问题。 我认为我得到了比接受的答案更简单的algorithm。
1. smax = maximum stock price from the list 2. then find the profit by assuming you have bought all the stocks till smax and you sell it at the price of smax 3. then check if smax is the last element of the stock price list if yes then return profit as answer, if no then make a new list containing stock prices after smax to the last stock price and repeat steps 1-3 and keep adding profit of each iteration to get the final profit.
从数组的末尾开始，不需要recursion
1. smax =名单中的最大股价
然后通过假设你已经买了所有的股票，直到smax，然后以smax的价格卖出来find利润
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numOfTestCase = sc.nextInt(); for (int i = 0; i < numOfTestCase; i++) { int n = sc.nextInt(); long profit = 0; int[] stockPrice = new int[n]; for (int j = 0; j < n; j++) { stockPrice[j] = sc.nextInt(); } int currMax = Integer.MIN_VALUE; for (int j = n - 1; j >= 0; j--) { if (currMax < stockPrice[j]) { currMax = stockPrice[j]; } profit += (currMax - stockPrice[j]); } System.out.println(profit); } }
你的逻辑是正确的…
卖在全球最大的's ..但recursion不是必需的…
如果ith元素是全球最大…在我之前卖出所有股票！
现在问题减less到以前的答案+我+ 1到N …
recursion是不需要的…线性地我们可以计算！
我的推理是，你在最高股票价格之前买入的每只股票都能获利。 使用这种思路，你可以在最高价格之前买入每一只股票，最大限度地卖出它，并且为剩下的股票价格重复同样的事情。
function profit(prices){ var totalStocks = 0, profitMade = 0; var buySell = function(sortedPrices){ for(var i = 0, len = sortedPrices.length; i < len; i++){ if (i < len - 1){ totalStocks++; profitMade = profitMade - sortedPrices[i]; }else{ profitMade = profitMade + totalStocks * sortedPrices[i]; totalStocks = 0; } } }, splitMaxPrice = function(rawPrices){ var leftStocks = rawPrices.splice(rawPrices.lastIndexOf(Math.max.apply(null, rawPrices))+1); buySell(rawPrices); if(leftStocks.length > 0){ splitMaxPrice(leftStocks); } return; }; splitMaxPrice(prices); return profitMade; }
