算法设计：通过最多买卖k次股票获得最大利润

2021年3月12日13:07:33 发表评论 865 次浏览

本文概述

在股票交易中, 买方在未来的某个日期购买股票并出售。给定股票价格为n天, 交易者最多可以进行k笔交易, 而新交易只能在上一次交易完成后才能开始, 请找出股票交易者可以赚取的最大利润。

例子：

Input:  
Price = [10, 22, 5, 75, 65, 80]
    K = 2
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 = [12, 14, 17, 10, 14, 13, 12, 15]
    K = 3
Output:  12
Trader earns 12 as the sum of 5, 4 and 3
Buy at price 12, sell at 17, buy at 10 
and sell at 14 and buy at 12 and sell
at 15
 
Input:  
Price = [100, 30, 15, 10, 8, 25, 80]
    K = 3
Output:  72
Only one transaction. Buy at price 8 
and sell at 80.

Input:  
Price = [90, 80, 70, 60, 50]
    K = 1
Output:  0
Not possible to earn.

有多种版本的问题。如果只允许我们买卖一次, 则可以使用两个元素之间的最大差额算法。如果我们最多只能进行2笔交易, 则可以按照讨论的方法进行这里。如果允许我们进行任意次数的买卖, 则可以遵循讨论的方法这里.

推荐：请在"实践首先, 在继续解决方案之前。

在这篇文章中, 我们只允许进行最多k笔交易。该问题可以通过使用动态编程来解决。

让利润[t] [i]表示直到第i天(包括第i天)最多使用t笔交易获得的最大利润。那么关系是：

利润[t] [i] =最大值(利润[t] [i-1], 最大值(价格[i] –价格[j] +利润[t-1] [j]))

对于范围[0, i-1]中的所有j

利润[t] [i]最高为–

  1. Profit [t] [i-1], 表示在第i天没有进行任何交易。
  2. 在第i天卖出的最大利润。为了在第i天卖出股票, 我们需要在[0, i – 1]天中的任何一天购买股票。如果我们在第j天买入股票, 然后在第i天卖出, 则最大获利将为价格[i] –价格[j] +利润[t-1] [j], 其中j在0到i-1之间变化。在这里, 利润[t-1] [j]最好, 直到第j天, 我们只需减少一笔交易即可完成。

以下是基于动态编程的实现。

C ++

// C++ program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
#include <climits>
#include <iostream>
using namespace std;
  
// Function to find out maximum profit by buying
// & selling a share atmost k times given stock
// price of n days
int maxProfit( int price[], int n, int k)
{
     // table to store results of subproblems
     // profit[t][i] stores maximum profit using
     // atmost t transactions up to day i (including
     // day i)
     int profit[k + 1][n + 1];
  
     // For day 0, you can't earn money
     // irrespective of how many times you trade
     for ( int i = 0; i <= k; i++)
         profit[i][0] = 0;
  
     // profit is 0 if we don't do any transation
     // (i.e. k =0)
     for ( int j = 0; j <= n; j++)
         profit[0][j] = 0;
  
     // fill the table in bottom-up fashion
     for ( int i = 1; i <= k; i++) {
         for ( int j = 1; j < n; j++) {
             int max_so_far = INT_MIN;
  
             for ( int m = 0; m < j; m++)
                 max_so_far = max(max_so_far, price[j] - price[m] + profit[i - 1][m]);
  
             profit[i][j] = max(profit[i][j - 1], max_so_far);
         }
     }
  
     return profit[k][n - 1];
}
  
// Driver code
int main()
{
     int k = 2;
     int price[] = { 10, 22, 5, 75, 65, 80 };
     int n = sizeof (price) / sizeof (price[0]);
  
     cout << "Maximum profit is: "
          << maxProfit(price, n, k);
  
     return 0;
}

Java

// Java program to find out maximum 
// profit by buying and selling a
// share atmost k times given
// stock price of n days
  
class GFG {
      
     // Function to find out 
     // maximum profit by 
     // buying & selling a 
     // share atmost k times
     // given stock price of n days
     static int maxProfit( int [] price, int n, int k)
     {
          
         // table to store results
         // of subproblems
         // profit[t][i] stores 
         // maximum profit using 
         // atmost t transactions up
         // to day i (including day i)
         int [][] profit = new int [k + 1 ][n + 1 ];
  
         // For day 0, you can't 
         // earn money irrespective
         // of how many times you trade
         for ( int i = 0 ; i <= k; i++)
             profit[i][ 0 ] = 0 ;
  
         // profit is 0 if we don't
         // do any transation
         // (i.e. k =0)
         for ( int j = 0 ; j <= n; j++)
             profit[ 0 ][j] = 0 ;
  
         // fill the table in 
         // bottom-up fashion
         for ( int i = 1 ; i <= k; i++) 
         {
             for ( int j = 1 ; j < n; j++)
             {
                 int max_so_far = 0 ;
  
                 for ( int m = 0 ; m < j; m++)
                 max_so_far = Math.max(max_so_far, price[j] -
                              price[m] + profit[i - 1 ][m]);
  
                 profit[i][j] = Math.max(profit[i] [j - 1 ], max_so_far);
             }
         }
  
         return profit[k][n - 1 ];
     }
  
     // Driver code 
     public static void main(String []args)
     {
         int k = 2 ;
         int [] price = { 10 , 22 , 5 , 75 , 65 , 80 };
         int n = price.length;
         System.out.println( "Maximum profit is: " + 
                             maxProfit(price, n, k));
     }
}
  
// This code is contributed by Anshul Aggarwal.

Python3

# Python program to maximize the profit
# by doing at most k transactions
# given stock prices for n days
  
# Function to find out maximum profit by
# buying & selling a share atmost k times 
# given stock price of n days
def maxProfit(prices, n, k):
      
     # Bottom-up DP approach
     profit = [[ 0 for i in range (k + 1 )]
                  for j in range (n)]
      
     # Profit is zero for the first
     # day and for zero transactions
     for i in range ( 1 , n):
          
         for j in range ( 1 , k + 1 ):
             max_so_far = 0
              
             for l in range (i):
                 max_so_far = max (max_so_far, prices[i] -
                             prices[l] + profit[l][j - 1 ])
                              
             profit[i][j] = max (profit[i - 1 ][j], max_so_far)
      
     return profit[n - 1 ][k]
  
# Driver code
k = 2
prices = [ 10 , 22 , 5 , 75 , 65 , 80 ]
n = len (prices)
  
print ( "Maximum profit is:" , maxProfit(prices, n, k))
  
# This code is contributed by vaibhav29498

C#

// C# program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
using System;
  
class GFG {
      
     // Function to find out maximum profit by 
     // buying & selling/ a share atmost k times
     // given stock price of n days
     static int maxProfit( int [] price, int n, int k)
     {
         // table to store results of subproblems
         // profit[t][i] stores maximum profit using atmost
         // t transactions up to day i (including day i)
         int [, ] profit = new int [k + 1, n + 1];
  
         // For day 0, you can't earn money
         // irrespective of how many times you trade
         for ( int i = 0; i <= k; i++)
             profit[i, 0] = 0;
  
         // profit is 0 if we don't do any transation
         // (i.e. k =0)
         for ( int j = 0; j <= n; j++)
             profit[0, j] = 0;
  
         // fill the table in bottom-up fashion
         for ( int i = 1; i <= k; i++) {
             for ( int j = 1; j < n; j++) {
                 int max_so_far = 0;
  
                 for ( int m = 0; m < j; m++)
                 max_so_far = Math.Max(max_so_far, price[j] -
                                price[m] + profit[i - 1, m]);
  
                 profit[i, j] = Math.Max(profit[i, j - 1], max_so_far);
             }
         }
  
         return profit[k, n - 1];
     }
  
     // Driver code to test above
     public static void Main()
     {
         int k = 2;
         int [] price = { 10, 22, 5, 75, 65, 80 };
  
         int n = price.Length;
  
         Console.Write( "Maximum profit is: " + 
                      maxProfit(price, n, k));
     }
}
  
// This code is contributed by Sam007

的PHP

<?php
// PHP program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
  
// Function to find out maximum profit by buying
// & selling a share atmost k times given stock
// price of n days
function maxProfit( $price , $n , $k )
{
      
     // table to store results of subproblems
     // profit[t][i] stores maximum profit using
     // atmost t transactions up to day i (including
     // day i)
     $profit [ $k + 1][ $n + 1] = 0;
      
     // For day 0, you can't earn money
     // irrespective of how many times you trade
     for ( $i = 0; $i <= $k ; $i ++)
         $profit [ $i ][0] = 0;
  
     // profit is 0 if we don't
     // do any transation
     // (i.e. k =0)
     for ( $j = 0; $j <= $n ; $j ++)
         $profit [0][ $j ] = 0;
  
     // fill the table in 
     // bottom-up fashion
     for ( $i = 1; $i <= $k ; $i ++) {
         for ( $j = 1; $j < $n ; $j ++) {
             $max_so_far = PHP_INT_MIN;
  
             for ( $m = 0; $m < $j ; $m ++)
                 $max_so_far = max( $max_so_far , $price [ $j ] - $price [ $m ] +
                               $profit [ $i - 1][ $m ]);
  
             $profit [ $i ][ $j ] = max( $profit [ $i ][ $j - 1], $max_so_far );
         }
     }
  
     return $profit [ $k ][ $n - 1];
}
  
     // Driver code
     $k = 2;
     $price = array (10, 22, 5, 75, 65, 80 );
     $n = sizeof( $price );
     echo "Maximum profit is: " . maxProfit( $price , $n , $k );
  
// This is contributed by mits
?>

输出：

Maximum profit is: 87

优化的解决方案：

上述解决方案的时间复杂度为O(k.n

2

)。如果我们能够计算出在固定时间的第i天卖出股票所获得的最大利润, 则可以减少该收益。

利润[t] [i] =最大值(利润[t] [i-1], 最大值(价格[i] –价格[j] +利润[t-1] [j])))

对于范围[0, i-1]中的所有j

如果我们仔细注意,

max(价格[i] –价格[j] +利润[t-1] [j])

对于范围[0, i-1]中的所有j

可以改写成

=价格[i] +最大值(利润[t-1] [j] –价格[j])

对于范围[0, i-1]中的所有j

=价格[i] +最大值(prevDiff, 利润[t-1] [i-1] –价格[i-1])

其中prevDiff为max(利润[t-1] [j] –价格[j])

对于范围[0, i-2]中的所有j

因此, 如果我们已经为范围[0, i-2]中的所有j计算了max(profit [t-1] [j] – price [j]), 则可以在恒定时间内为j = i – 1进行计算。换句话说, 我们不必再往回看[0, i-1]范围就可以找到购买的最佳日期。我们可以使用下面的修正关系确定恒定时间。

利润[t] [i] =最大值(利润[t] [i-1], 价格[i] +最大值(prevDiff, 利润[t-1] [i-1] –价格[i-1])

其中prevDiff是范围[0, i-2]中所有j的max(profit [t-1] [j] – price [j])

以下是其优化的实现–

C ++

// C++ program to find out maximum profit by buying
// and/ selling a share atmost k times given stock
// price of n days
#include <climits>
#include <iostream>
using namespace std;
  
// Function to find out maximum profit by buying &
// selling/ a share atmost k times given stock price
// of n days
int maxProfit( int price[], int n, int k)
{
     // table to store results of subproblems
     // profit[t][i] stores maximum profit using atmost
     // t transactions up to day i (including day i)
     int profit[k + 1][n + 1];
  
     // For day 0, you can't earn money
     // irrespective of how many times you trade
     for ( int i = 0; i <= k; i++)
         profit[i][0] = 0;
  
     // profit is 0 if we don't do any transation
     // (i.e. k =0)
     for ( int j = 0; j <= n; j++)
         profit[0][j] = 0;
  
     // fill the table in bottom-up fashion
     for ( int i = 1; i <= k; i++) {
         int prevDiff = INT_MIN;
         for ( int j = 1; j < n; j++) {
             prevDiff = max(prevDiff, profit[i - 1][j - 1] - price[j - 1]);
             profit[i][j] = max(profit[i][j - 1], price[j] + prevDiff);
         }
     }
  
     return profit[k][n - 1];
}
  
// Driver Code
int main()
{
     int k = 3;
     int price[] = { 12, 14, 17, 10, 14, 13, 12, 15 };
  
     int n = sizeof (price) / sizeof (price[0]);
  
     cout << "Maximum profit is: "
          << maxProfit(price, n, k);
  
     return 0;
}

Java

// Java program to find out maximum
// profit by buying and selling a
// share atmost k times given stock
// price of n days
import java.io.*;
  
class GFG {
      
     // Function to find out maximum profit by
     // buying & selling/ a share atmost k times 
     // given stock price of n days
     static int maxProfit( int price[], int n, int k)
     {
          
         // table to store results of subproblems
         // profit[t][i] stores maximum profit
         // using atmost t transactions up to day
         // i (including day i)
         int profit[][] = new int [k + 1 ][ n + 1 ];
  
         // For day 0, you can't earn money
         // irrespective of how many times you trade
         for ( int i = 0 ; i <= k; i++)
             profit[i][ 0 ] = 0 ;
  
         // profit is 0 if we don't do any 
         // transation (i.e. k =0)
         for ( int j = 0 ; j <= n; j++)
             profit[ 0 ][j] = 0 ;
  
         // fill the table in bottom-up fashion
         for ( int i = 1 ; i <= k; i++) 
         {
             int prevDiff = Integer.MIN_VALUE;
             for ( int j = 1 ; j < n; j++) 
             {
                 prevDiff = Math.max(prevDiff, profit[i - 1 ][j - 1 ] - 
                            price[j - 1 ]);
                 profit[i][j] = Math.max(profit[i][j - 1 ], price[j] + prevDiff);
             }
         }
  
         return profit[k][n - 1 ];
     }
  
// Driver code
public static void main (String[] args) 
     {
         int k = 3 ;
         int price[] = { 12 , 14 , 17 , 10 , 14 , 13 , 12 , 15 };
  
         int n = price.length;
  
         System.out.println( "Maximum profit is: " + 
                             maxProfit(price, n, k));
     }
} 
  
// This code is contributed by Sam007

Python3

# Python3 program to find out maximum 
# profit by buying and/ selling a share 
# at most k times given the stock price
# of n days 
  
# Function to find out maximum profit 
# by buying & selling/ a share atmost 
# k times given stock price of n days 
def maxProfit(price, n, k): 
  
     # Table to store results of subproblems 
     # profit[t][i] stores maximum profit 
     # using atmost t transactions up to 
     # day i (including day i) 
     profit = [[ 0 for i in range (n + 1 )] 
                  for j in range (k + 1 )] 
  
     # Fill the table in bottom-up fashion 
     for i in range ( 1 , k + 1 ): 
         prevDiff = float ( '-inf' )
          
         for j in range ( 1 , n): 
             prevDiff = max (prevDiff, profit[i - 1 ][j - 1 ] - 
                            price[j - 1 ]) 
             profit[i][j] = max (profit[i][j - 1 ], price[j] + prevDiff) 
  
     return profit[k][n - 1 ] 
  
# Driver Code 
if __name__ = = "__main__" :
  
     k = 3
     price = [ 12 , 14 , 17 , 10 , 14 , 13 , 12 , 15 ]
     n = len (price) 
  
     print ( "Maximum profit is:" , maxProfit(price, n, k)) 
  
# This code is contributed 
# by Rituraj Jain

C#

// C# program to find out maximum profit by buying
// and selling a share atmost k times given stock
// price of n days
using System;
  
class GFG {
      
     // Function to find out maximum profit by
     // buying & selling/ a share atmost k times 
     // given stock price of n days
     static int maxProfit( int [] price, int n, int k)
     {
         // table to store results of subproblems
         // profit[t][i] stores maximum profit using atmost
         // t transactions up to day i (including day i)
         int [, ] profit = new int [k + 1, n + 1];
  
         // For day 0, you can't earn money
         // irrespective of how many times you trade
         for ( int i = 0; i <= k; i++)
             profit[i, 0] = 0;
  
         // profit is 0 if we don't do any transation
         // (i.e. k =0)
         for ( int j = 0; j <= n; j++)
             profit[0, j] = 0;
  
         // fill the table in bottom-up fashion
         for ( int i = 1; i <= k; i++) {
             int prevDiff = int .MinValue;
             for ( int j = 1; j < n; j++) {
             prevDiff = Math.Max(prevDiff, profit[i - 1, j - 1] - price[j - 1]);
             profit[i, j] = Math.Max(profit[i, j - 1], price[j] + prevDiff);
             }
         }
  
         return profit[k, n - 1];
     }
  
     // Driver code to test above
     public static void Main()
     {
         int k = 3;
         int [] price = {12, 14, 17, 10, 14, 13, 12, 15};
  
         int n = price.Length;
  
         Console.Write( "Maximum profit is: " + 
                      maxProfit(price, n, k));
     }
}
  
// This code is contributed by Sam007

的PHP

<?php
// PHP program to find out maximum
// profit by buying and selling a 
// share atmost k times given stock
// price of n days
  
// Function to find out maximum
// profit by buying & selling a 
// share atmost k times given 
// stock price of n days
function maxProfit( $price , $n , $k )
{
      
     // table to store results 
     // of subproblems profit[t][i]
     // stores maximum profit using
     // atmost t transactions up to
     // day i (including day i)
     $profit [ $k + 1][ $n + 1]=0;
  
     // For day 0, you can't 
     // earn money irrespective
     // of how many times you trade
     for ( $i = 0; $i <= $k ; $i ++)
         $profit [ $i ][0] = 0;
  
     // profit is 0 if we don't
     // do any transation
     // (i.e. k =0)
     for ( $j = 0; $j <= $n ; $j ++)
         $profit [0][ $j ] = 0;
  
     // fill the table in
     // bottom-up fashion
     $prevDiff = NULL;
     for ( $i = 1; $i <= $k ; $i ++) {
         for ( $j = 1; $j < $n ; $j ++) {
             $prevDiff = max( $prevDiff , $profit [ $i - 1][ $j - 1] - 
                                                $price [ $j - 1]);
             $profit [ $i ][ $j ] = max( $profit [ $i ][ $j - 1], $price [ $j ] + $prevDiff );
         }
     }
     return $profit [ $k ][ $n - 1];
}
  
     // Driver Code
     $k = 3;
     $price = array (12, 14, 17, 10, 14, 13, 12, 15);
     $n = sizeof( $price );
     echo "Maximum profit is: "
          , maxProfit( $price , $n , $k );
  
// This code is contributed by nitin mittal
?>

输出：

Maximum profit is: 12

上述解决方案的时间复杂度为O(kn), 空间复杂度为O(nk)。当我们使用上一个事务的结果时, 空间复杂度可以进一步降低为O(n)。但是为了使文章易于阅读, 我们使用了O(kn)空间。

本文作者：阿迪亚·戈尔(Aditya Goel)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: