在日常股票交易中，买方在上午购买股票，并在同一天出售。如果交易者一天最多可以进行2笔交易，而第二笔交易只能在第一笔交易完成后开始（买入->卖出->买入->卖出）。根据全天的股票价格，找出一个股票交易者可以获得的最大利润。
null
例如：
Input: price[] = {10, 22, 5, 75, 65, 80}Output: 87Trader earns 87 as sum of 12, 75 Buy at 10, sell at 22, Buy at 5 and sell at 80Input: price[] = {2, 30, 15, 10, 8, 25, 80}Output: 100Trader earns 100 as sum of 28 and 72Buy at price 2, sell at 30, buy at 8 and sell at 80Input: price[] = {100, 30, 15, 10, 8, 25, 80};Output: 72Buy at price 8 and sell at 80.Input: price[] = {90, 80, 70, 60, 50}Output: 0Not possible to earn.
A. 简单解决方案 是考虑每个索引“i”并执行以下操作
最多两次交易的最大利润= 最大{一次交易和子阵列价格的最大利润[0..i]+ 一次交易和子阵列价格的最大利润[i+1..n-1]} i从0到n-1不等。
可以使用以下O（n）算法计算使用一个事务可能的最大值 两个元素之间的最大差异 这个 较小的数字后面会出现较大的元素 上述简单解的时间复杂度为O（n） 2. ).
我们可以使用以下方法来实现 有效解决方案 其思想是存储每个子阵列的最大可能利润，并在以下两个阶段解决问题。
1) 创建一个利润表[0..n-1]，并将其中的所有值初始化为0。 2) 从右向左遍历价格[]并更新利润[i]，使利润[i]将一笔交易可实现的最大利润存储在子数组价格[i..n-1]中 3) 从左向右遍历价格[]并更新利润[i]，使利润[i]存储最大利润，使利润[i]包含子数组价格[0..i]中两次交易的最大可实现利润。 4) 回报利润[n-1]
要执行步骤2，我们需要从右到左跟踪最高价格，要执行步骤3，我们需要从左到右跟踪最低价格。为什么我们要反向穿越？这个想法是为了节省空间，在第三步中，我们使用相同的数组用于两个目的，最多1个事务，最多2个事务。迭代i之后，数组利润[0..i]包含两个事务的最大利润，利润[i+1..n-1]包含两个事务的利润。
下面是上述想法的实现。
C++
// 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 code 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
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; } // Driver Code 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 */ |
Python3
# 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; } // Driver code 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 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 ?> |
Javascript
<script> // JavaScript 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 let profit = new Array(n); for (let 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. */ let max_price = price[n - 1]; for (let 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 let min_price = price[0]; for (let 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)); } let result = profit[n - 1]; return result; } // Driver code let price = [ 2, 30, 15, 10, 8, 25, 80 ]; let n = price.length; document.write( "Maximum Profit = " + maxProfit(price, n)); // This code is contributed by Surbhi Tyagi. </script> |
输出
Maximum Profit = 100
上述解的时间复杂度为O（n）。
算法范式：动态规划
使用谷-峰法计算这个问题还有一种方法，即取一个可变利润，并用零初始化，然后从第（i+1）个位置遍历价格[]数组，只要初始位置值大于之前的值，将其添加到可变利润中。
但这种方法在这个问题上不起作用，你只能买卖一只股票两次。例如 如果价格[]={2,4,2,4,2,4} 然后这种特殊的方法将给出结果 6. 而在这个给定的问题中，你只能做两个事务，所以答案应该是 4. 因此 这种方法只有在我们有机会进行无限交易时才有效。
C++
#include <iostream> using namespace std; int main() { int price[] = { 2, 30, 15, 10, 8, 25, 80 }; int n = 7; // adding array int profit = 0; // Initializing variable // valley-peak approach /* 80 / 30 / / 25 / 15 / / / 2 10 / / 8 */ for ( int i = 1; i < n; i++) { // traversing through array from (i+1)th // position int sub = price[i] - price[i - 1]; if (sub > 0) profit += sub; } cout << "Maximum Profit=" << profit; return 0; } // This code is contributed by RohitOberoi. |
JAVA
import java.util.*; class GFG { public static void main(String[] args) { int price[] = { 2 , 30 , 15 , 10 , 8 , 25 , 80 }; int n = 7 ; // adding array int profit = 0 ; // Initializing variable // valley-peak approach /* 80 / 30 / / 25 / 15 / / / 2 10 / / 8 */ for ( int i = 1 ; i < n; i++) { // traversing through array from (i+1)th // position int sub = price[i] - price[i - 1 ]; if (sub > 0 ) profit += sub; } System.out.print( "Maximum Profit=" + profit); } } // This code is contributed by umadevi9616 |
Python3
if __name__ = = '__main__' : price = [ 2 , 30 , 15 , 10 , 8 , 25 , 80 ] ; n = 7 ; # adding array profit = 0 ; # Initializing variable # valley-peak approach ''' 80 / 30 / / 25 / 15 / / / 2 10 / / 8 ''' for i in range ( 1 ,n): # traversing through array from (i+1)th # position sub = price[i] - price[i - 1 ]; if (sub > 0 ): profit + = sub; print ( "Maximum Profit=" ,profit); # This code is contributed by gauravrajput1 |
C#
using System; public class GFG { public static void Main(String[] args) { int []price = { 2, 30, 15, 10, 8, 25, 80 }; int n = 7; // adding array int profit = 0; // Initializing variable // valley-peak approach /* 80 / 30 / / 25 / 15 / / / 2 10 / / 8 */ for ( int i = 1; i < n; i++) { // traversing through array from (i+1)th // position int sub = price[i] - price[i - 1]; if (sub > 0) profit += sub; } Console.Write( "Maximum Profit=" + profit); } } // This code is contributed by gauravrajput1 |
Javascript
<script> var price = [ 2, 30, 15, 10, 8, 25, 80 ]; var n = 7; // adding array var profit = 0; // Initializing variable // valley-peak approach /* 80 / 30 / / 25 / 15 / / / 2 10 / / 8 */ for (i = 1; i < n; i++) { // traversing through array from (i+1)th // position var sub = price[i] - price[i - 1]; if (sub > 0) profit += sub; } document.write( "Maximum Profit=" + profit); // This code is contributed by gauravrajput1 </script> |
输出
Maximum Profit=100
时间和空间复杂度分别为O（n）和O（1）。
另一种方法：
初始化四个变量，用于处理第一次购买、第一次出售、第二次购买和第二次出售。将第一次购买和第二次购买设置为INT_MIN，第一次和第二次出售设置为0。这是为了确保从交易中获得利润。遍历数组并返回第二次销售，因为它将存储最大利润。
C++
#include <iostream> #include<climits> using namespace std; int maxtwobuysell( int arr[], int size) { int first_buy = INT_MIN; int first_sell = 0; int second_buy = INT_MIN; int second_sell = 0; for ( int i=0;i<size;i++) { first_buy = max(first_buy,-arr[i]); //we set prices to negative, so the calculation of profit will be convenient first_sell = max(first_sell,first_buy+arr[i]); second_buy = max(second_buy,first_sell-arr[i]); //we can buy the second only after first is sold second_sell = max(second_sell,second_buy+arr[i]); } return second_sell; } int main() { int arr[] = {2, 30, 15, 10, 8, 25, 80}; int size = sizeof (arr)/ sizeof (arr[0]); cout<<maxtwobuysell(arr,size); return 0; } |
JAVA
import java.util.*; class GFG{ static int maxtwobuysell( int arr[], int size) { int first_buy = Integer.MIN_VALUE; int first_sell = 0 ; int second_buy = Integer.MIN_VALUE; int second_sell = 0 ; for ( int i = 0 ; i < size; i++) { first_buy = Math.max(first_buy,-arr[i]); first_sell = Math.max(first_sell,first_buy+arr[i]); second_buy = Math.max(second_buy,first_sell-arr[i]); second_sell = Math.max(second_sell,second_buy+arr[i]); } return second_sell; } public static void main(String[] args) { int arr[] = { 2 , 30 , 15 , 10 , 8 , 25 , 80 }; int size = arr.length; System.out.print(maxtwobuysell(arr,size)); } } // This code is contributed by gauravrajput1 |
Python3
import sys def maxtwobuysell(arr, size): first_buy = - sys.maxsize; first_sell = 0 ; second_buy = - sys.maxsize; second_sell = 0 ; for i in range (size): first_buy = max (first_buy, - arr[i]); first_sell = max (first_sell, first_buy + arr[i]); second_buy = max (second_buy, first_sell - arr[i]); second_sell = max (second_sell, second_buy + arr[i]); return second_sell; if __name__ = = '__main__' : arr = [ 2 , 30 , 15 , 10 , 8 , 25 , 80 ]; size = len (arr); print (maxtwobuysell(arr, size)); # This code is contributed by gauravrajput1 |
C#
using System; public class GFG{ static int maxtwobuysell( int []arr, int size) { int first_buy = int .MinValue; int first_sell = 0; int second_buy = int .MinValue; int second_sell = 0; for ( int i = 0; i < size; i++) { first_buy = Math.Max(first_buy,-arr[i]); first_sell = Math.Max(first_sell,first_buy+arr[i]); second_buy = Math.Max(second_buy,first_sell-arr[i]); second_sell = Math.Max(second_sell,second_buy+arr[i]); } return second_sell; } public static void Main(String[] args) { int []arr = {2, 30, 15, 10, 8, 25, 80}; int size = arr.Length; Console.Write(maxtwobuysell(arr,size)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> function maxtwobuysell(arr , size) { var first_buy = -1000; var first_sell = 0; var second_buy = -1000; var second_sell = 0; for ( var i = 0; i < size; i++) { first_buy = Math.max(first_buy, -arr[i]); first_sell = Math.max(first_sell, first_buy + arr[i]); second_buy = Math.max(second_buy, first_sell - arr[i]); second_sell = Math.max(second_sell, second_buy + arr[i]); } return second_sell; } var arr = [ 2, 30, 15, 10, 8, 25, 80 ]; var size = arr.length; document.write(maxtwobuysell(arr, size)); // This code is contributed by gauravrajput1 </script> |
输出
100
时间复杂性： O（N）
辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
