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

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

## 本文概述

``````Input:
Price = [10, 22, 5, 75, 65, 80]
K = 2
Output:  87
Trader earns 87 as sum of 12 and 75
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
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.``````

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

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

2

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

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

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

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

## 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``