本文概述在股票交易中, 买方在未来的某个日期购买股票并出售。给定股票价格为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 80Input: 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 daysclass 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 = 0for 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)空间。
【算法设计（通过最多买卖k次股票获得最大利润）】本文作者：阿迪亚·戈尔(Aditya Goel)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  tx2440学习--ads写点灯程序遇到的问题
• 

  部落徽记在哪里买
• 

  科沃斯售后电话，科沃斯智能扫地机售后维修站郑州
• 

  玄武岩的用途有哪些 玄武岩的用途有哪些特点
• 

  膳食结构的类型
• 

  公众号怎么挣钱 运营公众号怎么赚钱
• 

  od 易语言分析插件
• 

  保持通话|华为Mate50Pro渲染图：2亿液态主摄+1.8英寸辅屏，骁龙898最诱人
• 

  什么是狗头金？
• 

  An Interactive 3D Viewer
• 

  乙型肝炎病毒表面抗体是什么意思
• 

  鼻塞怎么办怎样让鼻通气？鼻塞怎么办呢快速缓解
• 

  怎么样正确选用中成药
• 

  肝癌|老戏骨吴孟达患肝癌入院，晚期肝癌还有希望吗？这里告诉你答案
• 

  mysql的日志文件默认在哪里 mysql日志开关
• 

  2023如何领取连云港4A级景区免费电子门票？时间+入口
• 

  zookeeper概述及下载 - 雨中散步撒哈拉
• 

  西瓜坐瓜率低的解决方法 西瓜瓜型不好如何管理
• 

  戴尔14r
• 

  halt怎么读 envelope怎么读

• 文件处理（如何在Python中读取文件（））
• TypeScript中的变量编程介绍
• PHP Ds Map diff()函数用法解读
• PHP内置函数dir()函数用法介绍
• jQuery Highcharts插件介绍和用法示例
• Xamarin开发人员的Nagarro面试体验| 3年经验
• 算法（Python程序查找列表的累积和）
• VueJS指令v-bind、v-model和其它数据绑定全解
• 一个例子搞定！VueJS监控属性watch用法和例子详解