در معاملات روزمره، یک خریدار، سهام‌های خود را صبح می‌خرد و آن‌ها را در روز مشابهی می‌فروشد. اگر معامله‌گر امکان انجام حداکثر دو تراکنش را در یک روز داشته باشد، دومین تراکنش درست لحظه‌ای انجام می‌شود که تراکنش اول کامل است (فروش > خرید > فروش‌ > خرید). قیمت‌های سهام در طی یک روز داده شده است و هدف یافتن بیشینه سودی است که معامله‌گر یک سهم می‌تواند داشته باشد. مثال زیر به درک بهتر این مطلب کمک خواهد کرد.

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) ‎ قابل محاسبه است. بیشینه تفاوت بین دو عنصر به گونه‌ای است که عنصر بزرگ‌تر پس از عدد کوچک‌تری به وقوع می‌پیوندد. پیچیدگی زمانی راهکار ساده بالا برابر با O(n²)‎ است. می‌توان این کار را با راهکار بهینه‌تری که در ادامه بیان شده است، در زمان O(n)‎ انجام داد. هدف ذخیره‌سازی بیشینه سود ممکن برای هر زیر آرایه و حل مسئله در دو فازی است که در ادامه بیان شده‌اند.

1. ساخت جدول profit[0..n-1]‎ و مقداردهی اولیه همه مقادیر به ۰.
2. پیمایش price[]‎ از راست به چپ و به روز رسانی profit[i]‎ به گونه‌ای که profit[i]‎ بیشینه سود قابل حصول از یک تراکنش را در زیر آرایه price[i..n-1]‎ ذخیره کند.
3. پیمایش price[]‎ از چپ به راست و به روز رسانی profit[i]‎ به گونه‌ای که profit[i]‎ بیشینه سود را ذخیره می‌کند، به طوری که profit[i]‎ حاوی بیشینه سود از دو تراکنش در زیر آرایه price[0..i]‎ است.
4. بازگرداندن profit[n-1]‎

برای انجام گام ۲، نیاز به پیگیری بیشینه قیمت‌ها از چپ به راست است. چرا پیمایش در جهت معکوس انجام می‌شود؟ هدف ذخیره‌سازی فضا است، در گام سوم، از آرایه مشابهی برای هر دو هدف استفاده می‌شود که بیشینه با ۱ تراکنش و بیشینه با ۲ تراکنش. پس از تکرار i، آرایه profit[0..i]‎ حاوی بیشینه سود با دو تراکنش و profit[i+1..n-1]‎ حاوی سود با دو تراکنش است. در ادامه، پیاده‌سازی رویکرد بالا انجام شده است.

پیاده‌سازی در ++C

// C++ program to find maximum possible profit with at most 
// two transactions 
#include<iostream> 
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; 
}

پیاده‌سازی در جاوا

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 */

پیاده‌سازی در پایتون

# 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

// 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, 
                                  ۸, ۲۵, ۸۰}; 
        int n = price.Length; 
          
        Console.Write("Maximum Profit = "
                      + maxProfit(price, n)); 
    } 
} 
  
// This code is contributed by nitin mittal. 

پیاده‌سازی در 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, 
               ۸, ۲۵, ۸۰);  
$n = sizeof($price);  
echo "Maximum Profit = ".  
      maxProfit($price, $n);  
      
// This code is contributed 
// by Arnab Kundu 
?>

خروجی قطعه کد بالا به صورت زیر است.

Maximum Profit = 100

پیچیدگی زمانی بالا از درجه O(n)‎ است. پاردایم الگوریتمی مورد استفاده برای روش بالا، «برنامه‌نویسی پویا» (Dynamic Programming) است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

منبع [+]