# 通過最多買賣兩次股份獲得最大利潤 > 原文： [https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-twice/](https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-twice/) 在每日股票交易中，買主在早上購買股票并在同一天出售。 如果允許交易者一天最多進行兩筆交易，而第二筆交易只能在第一筆交易完成后才能開始（賣出->買入->賣出->買入）。 給定全天股價，找出股票交易者可以賺取的最大利潤。 **示例**： ``` Input: price[] = {10, 22, 5, 75, 65, 80} Output: 87 Trader earns 87 as sum of 12 and 75 Buy at price 10, sell at 22, buy at 5 and sell at 80 Input: price[] = {2, 30, 15, 10, 8, 25, 80} Output: 100 Trader earns 100 as sum of 28 and 72 Buy at price 2, sell at 30, buy at 8 and sell at 80 Input: price[] = {100, 30, 15, 10, 8, 25, 80}; Output: 72 Buy at price 8 and sell at 80. Input: price[] = {90, 80, 70, 60, 50} Output: 0 Not possible to earn. ``` **簡單解決方案**是考慮每個索引“ i”，然后執行以下操作 ``` Max profit with at most two transactions = MAX {max profit with one transaction and subarray price[0..i] + max profit with one transaction and aubarray price[i+1..n-1] } i varies from 0 to n-1\. ``` 可以使用以下`O(n)`算法計算一次交易的最大可能金額 [兩個元素之間的最大差異，使得較大的元素出現在較小的數字之后](https://www.geeksforgeeks.org/maximum-difference-between-two-elements/) 上述簡單解的時間復雜度為 `O(n^2)`。 我們可以使用以下**有效解**來實現`O(n)`。 想法是存儲每個子數組的最大可能利潤，并在接下來的兩個階段中解決問題。 **1）**創建一個表 profit [0..n-1]并初始化其中的所有值 0。 **2）**從右到左遍歷價格[]并更新利潤[i]，以使利潤[i]在子數組價格[i..n-1]中存儲可從一次交易獲得的最大利潤。 **3）**從左到右遍歷價格[]并更新利潤[i]，以使利潤[i]存儲最大利潤，從而使利潤[i]包含子數組價格[0]中兩次交易的最大可實現利潤。 。一世]。 **4）**回報利潤[n-1] 要執行步驟 2，我們需要從右到左跟蹤最大價格，而要執行步驟 3，我們需要從左到右跟蹤最小價格。 為什么我們要反向走？ 這個想法是為了節省空間，在第三步中，我們為兩個目的使用相同的數組，最多 1 個事務，最大 2 個事務。 在迭代 i 之后，數組 Profit [0..i]包含 2 個事務的最大利潤，而 Profit [i + 1..n-1]包含 2 個事務的利潤。 以下是上述想法的實現。 ## C++ ```cpp // C++ program to find maximum possible profit with at most // two transactions #include<bits/stdc++.h> using namespace std; // Returns maximum profit with two transactions on a given // list of stock prices, price[0..n-1] int maxProfit(int price[], int n) { ????// Create profit array and initialize it as 0 ????int *profit = new int[n]; ????for (int i=0; i<n; i++) ????????profit[i] = 0; ????/* Get the maximum profit with only one transaction ???????allowed. After this loop, profit[i] contains maximum ???????profit from price[i..n-1] using at most one trans. */ ????int max_price = price[n-1]; ????for (int i=n-2;i>=0;i--) ????{ ????????// max_price has maximum of price[i..n-1] ????????if (price[i] > max_price) ????????????max_price = price[i]; ????????// we can get profit[i] by taking maximum of: ????????// a) previous maximum, i.e., profit[i+1] ????????// b) profit by buying at price[i] and selling at ????????//??? max_price ????????profit[i] = max(profit[i+1], max_price-price[i]); ????} ????/* Get the maximum profit with two transactions allowed ???????After this loop, profit[n-1] contains the result */ ????int min_price = price[0]; ????for (int i=1; i<n; i++) ????{ ????????// min_price is minimum price in price[0..i] ????????if (price[i] < min_price) ????????????min_price = price[i]; ????????// Maximum profit is maximum of: ????????// a) previous maximum, i.e., profit[i-1] ????????// b) (Buy, Sell) at (min_price, price[i]) and add ????????//??? profit of other trans. stored in profit[i] ????????profit[i] = max(profit[i-1], profit[i] + ????????????????????????????????????(price[i]-min_price) ); ????} ????int result = profit[n-1]; ????delete [] profit; // To avoid memory leak ????return result; } // Driver program int main() { ????int price[] = {2, 30, 15, 10, 8, 25, 80}; ????int n = sizeof(price)/sizeof(price[0]); ????cout << "Maximum Profit = " << maxProfit(price, n); ????return 0; } ``` ## Java ```java class Profit { ????// Returns maximum profit with two transactions on a given ????// list of stock prices, price[0..n-1] ????static int maxProfit(int price[], int n) ????{ ????????// Create profit array and initialize it as 0 ????????int profit[] = new int[n]; ????????for (int i=0; i<n; i++) ????????????profit[i] = 0; ????????/* Get the maximum profit with only one transaction ???????????allowed. After this loop, profit[i] contains maximum ???????????profit from price[i..n-1] using at most one trans. */ ????????int max_price = price[n-1]; ????????for (int i=n-2;i>=0;i--) ????????{ ????????????// max_price has maximum of price[i..n-1] ????????????if (price[i] > max_price) ????????????????max_price = price[i]; ????????????// we can get profit[i] by taking maximum of: ????????????// a) previous maximum, i.e., profit[i+1] ????????????// b) profit by buying at price[i] and selling at ????????????//??? max_price ????????????profit[i] = Math.max(profit[i+1], max_price-price[i]); ????????} ????????/* Get the maximum profit with two transactions allowed ???????????After this loop, profit[n-1] contains the result */ ????????int min_price = price[0]; ????????for (int i=1; i<n; i++) ????????{ ????????????// min_price is minimum price in price[0..i] ????????????if (price[i] < min_price) ????????????????min_price = price[i]; ????????????// Maximum profit is maximum of: ????????????// a) previous maximum, i.e., profit[i-1] ????????????// b) (Buy, Sell) at (min_price, price[i]) and add ????????????//??? profit of other trans. stored in profit[i] ????????????profit[i] = Math.max(profit[i-1], profit[i] + ????????????????????????????????????????(price[i]-min_price) ); ????????} ????????int result = profit[n-1]; ????????return result; ????} ????public static void main(String args[]) ????{ ????????int price[] = {2, 30, 15, 10, 8, 25, 80}; ????????int n = price.length; ????????System.out.println("Maximum Profit = "+ maxProfit(price, n)); ????} }/* This code is contributed by Rajat Mishra */ ``` ## Python ``` # Returns maximum profit with two transactions on a given? # list of stock prices price[0..n-1] def maxProfit(price,n): ????# Create profit array and initialize it as 0 ????profit = [0]*n ????# Get the maximum profit with only one transaction ????# allowed. After this loop, profit[i] contains maximum ????# profit from price[i..n-1] using at most one trans. ????max_price=price[n-1] ????for i in range( n-2, 0 ,-1): ????????if price[i]> max_price: ????????????max_price = price[i] ????????# we can get profit[i] by taking maximum of: ????????# a) previous maximum, i.e., profit[i+1] ????????# b) profit by buying at price[i] and selling at ????????#??? max_price ????????profit[i] = max(profit[i+1], max_price - price[i]) ????# Get the maximum profit with two transactions allowed ????# After this loop, profit[n-1] contains the result???? ????min_price=price[0] ????for i in range(1,n): ????????if price[i] < min_price: ????????????min_price = price[i] ????????# Maximum profit is maximum of: ????????# a) previous maximum, i.e., profit[i-1] ????????# b) (Buy, Sell) at (min_price, A[i]) and add ????????#??? profit of other trans. stored in profit[i]???? ????????profit[i] = max(profit[i-1], profit[i]+(price[i]-min_price)) ????result = profit[n-1] ????return result # Driver function price = [2, 30, 15, 10, 8, 25, 80] print "Maximum profit is", maxProfit(price, len(price)) # This code is contributed by __Devesh Agrawal__ ``` ## C# ```cs // C# program to find maximum possible profit // with at most two transactions using System; class GFG { ????// Returns maximum profit with two ????// transactions on a given list of? ????// stock prices, price[0..n-1] ????static int maxProfit(int []price, int n) ????{ ????????// Create profit array and initialize ????????// it as 0 ????????int []profit = new int[n]; ????????for (int i = 0; i < n; i++) ????????????profit[i] = 0; ????????/* Get the maximum profit with only ????????one transaction allowed. After this? ????????loop, profit[i] contains maximum ????????profit from price[i..n-1] using at ????????most one trans. */ ????????int max_price = price[n-1]; ????????for (int i = n-2; i >= 0; i--) ????????{ ????????????// max_price has maximum of ????????????// price[i..n-1] ????????????if (price[i] > max_price) ????????????????max_price = price[i]; ????????????// we can get profit[i] by taking? ????????????// maximum of: ????????????// a) previous maximum, i.e.,? ????????????// profit[i+1] ????????????// b) profit by buying at price[i] ????????????// and selling at max_price ????????????profit[i] = Math.Max(profit[i+1],? ??????????????????????????max_price - price[i]); ????????} ????????/* Get the maximum profit with two ????????transactions allowed After this loop, ????????profit[n-1] contains the result */ ????????int min_price = price[0]; ????????for (int i = 1; i < n; i++) ????????{ ????????????// min_price is minimum price in ????????????// price[0..i] ????????????if (price[i] < min_price) ????????????????min_price = price[i]; ????????????// Maximum profit is maximum of: ????????????// a) previous maximum, i.e., ????????????// profit[i-1] ????????????// b) (Buy, Sell) at (min_price, ????????????// price[i]) and add profit of? ????????????// other trans. stored in ????????????// profit[i] ????????????profit[i] = Math.Max(profit[i-1], ???????????????????????profit[i] + (price[i] ??????????????????????????????- min_price) ); ????????} ????????int result = profit[n-1]; ????????return result; ????} ????public static void Main() ????{ ????????int []price = {2, 30, 15, 10, ??????????????????????????????????8, 25, 80}; ????????int n = price.Length; ????????Console.Write("Maximum Profit = " ??????????????????????+ maxProfit(price, n)); ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // PHP program to find maximum? // possible profit with at most? // two transactions // Returns maximum profit with? // two transactions on a given? // list of stock prices, price[0..n-1]? function maxProfit($price, $n)? { ????// Create profit array and ????// initialize it as 0? ????$profit = array();? ????for ($i = 0; $i < $n; $i++)? ????????$profit[$i] = 0;? ????// Get the maximum profit with? ????// only one transaction allowed. ????// After this loop, profit[i] ????// contains maximum profit from? ????// price[i..n-1] using at most? ????// one trans.? ????$max_price = $price[$n - 1];? ????for ($i = $n - 2; $i >= 0; $i--)? ????{? ????????// max_price has maximum? ????????// of price[i..n-1]? ????????if ($price[$i] > $max_price)? ????????????$max_price = $price[$i];? ????????// we can get profit[i] by? ????????// taking maximum of:? ????????// a) previous maximum,? ????????//??? i.e., profit[i+1]? ????????// b) profit by buying at? ????????// price[i] and selling at? ????????// max_price? ????????if($profit[$i + 1] > ???????????$max_price-$price[$i]) ????????$profit[$i] = $profit[$i + 1];? ????????else ????????$profit[$i] = $max_price - ??????????????????????$price[$i]; ????}? ????// Get the maximum profit with? ????// two transactions allowed.? ????// After this loop, profit[n-1]? ????// contains the result? ????$min_price = $price[0];? ????for ($i = 1; $i < $n; $i++)? ????{? ????????// min_price is minimum? ????????// price in price[0..i]? ????????if ($price[$i] < $min_price)? ????????????$min_price = $price[$i];? ????????// Maximum profit is maximum of:? ????????// a) previous maximum,? ????????//??? i.e., profit[i-1]? ????????// b) (Buy, Sell) at (min_price,? ????????//???? price[i]) and add? ????????// profit of other trans.? ????????// stored in profit[i]? ????????$profit[$i] = max($profit[$i - 1],? ??????????????????????????$profit[$i] +? ?????????????????????????($price[$i] - $min_price));? ????}? ????$result = $profit[$n - 1];? ????return $result;? } // Driver Code? $price = array(2, 30, 15, 10, ???????????????8, 25, 80);? $n = sizeof($price);? echo "Maximum Profit = ".? ??????maxProfit($price, $n);? // This code is contributed // by Arnab Kundu ?> ``` **輸出**： ``` Maximum Profit = 100 ``` 上述解決方案的時間復雜度為`O(n)`。 算法范例：動態編程