對於給定的股票利潤最大化報價

Question

有人問我這個問題，而面試啓動，並在

Code Sprint:systems

**的問題在最近的比賽再次看到了這一點：

您將得到股票價格一整天。每一天，您都可以購買一單位的股票，出售您已經購買的任何數量的股票單位，或者什麼也不做。什麼是你可以通過優化計劃你的交易策略獲取最大的利潤？**

例子（即無天可以改變輸入）

5 3 2 =>利潤= 0 //因爲價格降低每一天，最大利潤我們可以= 0

1 2 100 =>利潤= 197

1 3 1 2 =>利潤= 3 //我們在買賣1在3，則我們購買在1和銷售2 ..總利潤= 3

我的解決方案：

a）找到股票價格最大的那一天。直到當天繼續購買1單位的股票。

b）若該日是最後一天然後退出：

其他： 賣當日所有股票和那一天後陣列分裂和其餘元素遞歸
C）合併利潤

如1 4 1 2 3
一）最高股價第2天..所以我們買的第1天的股票和賣出第2天（利潤= 3），那麼我們遞歸的剩餘天數：1 2 3

b）最高價格爲3（當日5），所以我們繼續購買第3天，第4天的股票和賣出第5天（利潤=（3×2 - 3 = 3）

三）利潤總額= 3 + 3 = 6

的複雜性原來這是O（n^2）。這個解決方案通過了11個案例中的10個，但超過了最後一個測試案例的時間限制（即最大的輸入）

所以我的問題是誰能想到一個更有效的解決方案來解決這個問題？有動態編程解決方案嗎？

P.S：這是我第一次在這裏問一個問題。所以請讓我知道如果我需要改進/添加這個問題的東西

Answer 1

我同意你的方法的邏輯，但沒有必要做遞歸處理或全局最大值搜索。要找到賣/買天，你只需要每天看一次：

訣竅是從頭開始。 如果您的旅行時間倒退，股票交易很容易！

如果你覺得代碼更容易比文字閱讀，只跳過我的解釋，但在這裏有雲：

從最終讀書，看當天的價格。這是迄今爲止的最高價格（從最終），然後出售！最後一天（我們開始閱讀的那一天）你會一直賣。

然後轉到第二天（記住，時間倒退）。迄今爲止最高的價格（從我們所看到的全部）？ - 然後全部賣掉，你不會找到更好的一天。否則價格會上漲，所以買。以同樣的方式繼續直到開始。

整個問題用解決一個單一的反向循環：計算交易的決定和利潤。

下面是在C-像Python代碼：（我可以避免大多數Python的東西應該爲一個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：在該點之後，我們有降低或穩定的價格，並且沒有買入。

您可以驗證該利潤計算是一個簡單的循環，正確的（爲簡單起見想象這是上面的函數內）

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) 

Answer 2

另一種方式來看待它：
在預處理，每個元素a[i]找到a[j] st j > i和它最大限度(a[j] - a[i])
如此，最佳你可以在a[i]以優惠的價格做的是買得a[i]和a[j]銷售。如果不存在a[j] s.t. 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]是指您應該賣A [1]的價格。

總結總利潤：O(N)

long long int Profit = 0; 
    for(int i=0;i<N;++i) 
      Profit += max(0, (S[i]-A[i])); 

Answer 3

你的邏輯是正確的......在全球maxima's..but遞歸不需要

賣...

如果第i個元素是全球最大...在我之前賣出所有股票！

現在的問題減少到以前的答案+ I + 1到N ......不需要

遞歸...線性我們可以計算出！

Answer 4

我剛剛在比賽現場解決了這個問題。我想我得到了比接受的答案更簡單的算法。

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. 

Answer 5

從陣列端0.Start所以沒有必要遞歸
1. SMAX =最大的股票價格從列表
2.然後通過假設你已經購買了所有的股票，直到找到利潤SMAX 和你SMAX

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


      } 
    } 

Answer 6

我的理由是價格賣的話，你賺錢的每一隻股票的最高股價之前，買走。使用這種思路，您可以在最高價格之前購買每隻股票，最大限度地出售，並對剩餘股票價格重複相同的操作。

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; 

} 

Answer 7

這項任務的另一種O（n）的解決方案可以通過使用本地的最小和最大發現最大值和最小值之間的最佳尊重（利潤）明知最大應該有更大然後指數分鐘來完成。我們還需要查看以前最好的本地分鐘（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]); 
    } 

Answer 8

這裏更簡單易懂的算法;

private static void BuyOnceAndSellONce() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int profit = 0; 
     int minimumPrice = int.MaxValue; 
     for (int i = 0; i < stock.Length; i++) 
     { 
      profit = Math.Max(profit, stock[i] - minimumPrice); 
      minimumPrice = Math.Min(stock[i], minimumPrice); 

     } 
     Console.WriteLine("profit " + profit); 
    } 

    private static void MultipleBuySellButNonOverlappingTransactions() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int totalProfit = 0; 
     int currentProfit = 0; 
     for (int i = 1; i < stock.Length;i++) 
     { 
      currentProfit = stock[i] - stock[i - 1]; 
      if (currentProfit > 0) 
       totalProfit += currentProfit; 
     } 

     Console.WriteLine(totalProfit); 
    }