In daily share trading, a buyer buys shares in the morning and sells them on the same day. If the trader is allowed to make at most 2 transactions in a day, the second transaction can only start after the first one is complete (Buy->sell->Buy->sell). Given stock prices throughout the day, find out the maximum profit that a share trader could have made.
Examples:
Input: price[] = {10, 22, 5, 75, 65, 80}
Output: 87
Trader 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: 100
Trader earns 100 as sum of 28 and 72
Buy at price 2, sell at 30, buy at 8 and sell at 80Input: 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.
Naive approach: A Simple Solution is to consider every index ‘i’ and do the following
Max profit with at most two transactions =
MAX {max profit with one transaction and subarray price[0..i] +
max profit with one transaction and subarray price[i+1..n-1] }
i varies from 0 to n-1.
The maximum possible using one transaction can be calculated using the following O(n) algorithm
The maximum difference between two elements such that the larger element appears after the smaller number
Time Complexity: O(n2).
Efficient Solution. The idea is to store the maximum possible profit of every subarray and solve the problem in the following two phases.
1) Create a table profit[0..n-1] and initialize all values in it 0.
2) Traverse price[] from right to left and update profit[i] such that profit[i] stores maximum profit achievable from one transaction in subarray price[i..n-1]
3) Traverse price[] from left to right and update profit[i] such that profit[i] stores maximum profit such that profit[i] contains maximum achievable profit from two transactions in subarray price[0..i].
4) Return profit[n-1]
To do step 2, we need to keep track of the maximum price from right to left side, and to do step 3, we need to keep track of the minimum price from left to right. Why we traverse in reverse directions? The idea is to save space, in the third step, we use the same array for both purposes, maximum with 1 transaction and maximum with 2 transactions. After iteration i, the array profit[0..i] contains the maximum profit with 2 transactions, and profit[i+1..n-1] contains profit with two transactions.
Below are the implementations of the above approach.
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 codeint 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
import java.io.*;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 functionprice = [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 transactionsusing 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 codelet 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> |
Output
Maximum Profit = 100
Time complexity: O(n)
Auxiliary space: O(n)
Algorithmic Paradigm: Dynamic Programming
Another approach:
Initialize four variables for taking care of the first buy, first sell, second buy, second sell. Set first buy and second buy as INT_MIN and first and second sell as 0. This is to ensure to get profit from transactions. Iterate through the array and return the second sell as it will store maximum profit.
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 sysdef 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> |
Output
100
Time Complexity: O(N)
Auxiliary Space: O(1)
Recursive Approach :
Every day, We have two choices: Buy/Sell this stock OR ignore it and move to the next one.
Along with day, we also need to maintain a capacity variable which will tell us how many transactions
are remaining and it will be of which type (Buy or Sell) .According to that we will make
recursive calls and calculate the answer
We can do at most 4 transactions (Buy, Sell, Buy, Sell) in this order.
C++
#include <bits/stdc++.h>using namespace std;int f(int idx, int buy, int prices[], int cap, int n){ if (cap == 0) { return 0; } if (idx == n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = max(-prices[idx] + f(idx + 1, 1, prices, cap, n), f(idx + 1, 0, prices, cap, n)); } // you can either sell or not sell else { profit = max( prices[idx] + f(idx + 1, 0, prices, cap - 1, n), f(idx + 1, 1, prices, cap, n)); } return profit;}int maxtwobuysell(int prices[], int n){ return f(0, 0, prices, 2, n);}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.*;public class Main { static int f(int idx, int buy, int prices[], int cap, int n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.max(-prices[idx] + f(idx + 1, 1, prices, cap, n), f(idx + 1, 0, prices, cap, n)); } // you can either sell or not sell else { profit = Math.max( prices[idx] + f(idx + 1, 0, prices, cap - 1, n), f(idx + 1, 1, prices, cap, n)); } return profit; } static int maxtwobuysell(int prices[], int n) { return f(0, 0, prices, 2, n); } public static void main(String[] args) { int arr[] = { 2, 30, 15, 10, 8, 25, 80 }; int size = arr.length; System.out.println(maxtwobuysell(arr, size)); }}// This code is contributed by prajwalkandekar123. |
Python3
def f(idx, buy, prices, cap, n): if cap == 0: return 0 if idx == n: return 0 profit = 0 # you can either buy or not buy if buy == 0: profit = max(-prices[idx] + f(idx + 1, 1, prices, cap, n), f(idx + 1, 0, prices, cap, n)) # you can either sell or not sell else: profit = max(prices[idx] + f(idx + 1, 0, prices, cap - 1, n), f(idx + 1, 1, prices, cap, n)) return profitdef maxtwobuysell(prices, n): return f(0, 0, prices, 2, n)if __name__ == "__main__": arr = [2, 30, 15, 10, 8, 25, 80] size = len(arr) print(maxtwobuysell(arr, size)) # This code is contributed by prajwalkandekar123. |
Javascript
function f(idx, buy, prices, cap, n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } let profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.max( -prices[idx] + f(idx + 1, 1, prices, cap, n), f(idx + 1, 0, prices, cap, n) ); } // you can either sell or not sell else { profit = Math.max( prices[idx] + f(idx + 1, 0, prices, cap - 1, n), f(idx + 1, 1, prices, cap, n) ); } return profit;}function maxtwobuysell(prices, n) { return f(0, 0, prices, 2, n);}const arr = [2, 30, 15, 10, 8, 25, 80];const size = arr.length;console.log(maxtwobuysell(arr, size)); |
C#
using System;class MainClass { public static int f(int idx, int buy, int[] prices, int cap, int n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.Max( -prices[idx] + f(idx + 1, 1, prices, cap, n), f(idx + 1, 0, prices, cap, n)); } // you can either sell or not sell else { profit = Math.Max( prices[idx] + f(idx + 1, 0, prices, cap - 1, n), f(idx + 1, 1, prices, cap, n)); } return profit; } public static int maxtwobuysell(int[] prices, int n) { return f(0, 0, prices, 2, n); } public static void Main() { int[] arr = new int[] { 2, 30, 15, 10, 8, 25, 80 }; int size = arr.Length; Console.WriteLine(maxtwobuysell(arr, size)); }} |
Output
100
Time Complexity : O(2^N)
Auxiliary Space : O(N)
Memoization Approach:
Exact same code as above just store the answer of all states to avoid solving subproblems that have already been solved
C++
#include <bits/stdc++.h>using namespace std;int f(int idx, int buy, int prices[], vector<vector<vector<int> > >& dp, int cap, int n){ if (cap == 0) { return 0; } if (idx == n) { return 0; } if (dp[idx][buy][cap] != -1) { return dp[idx][buy][cap]; } int profit = 0; // you can either buy or not buy if (buy == 0) { dp[idx][buy][cap] = profit = max(-prices[idx] + f(idx + 1, 1, prices, dp, cap, n), f(idx + 1, 0, prices, dp, cap, n)); } // you can either sell or not sell else { dp[idx][buy][cap] = profit = max( prices[idx] + f(idx + 1, 0, prices, dp, cap - 1, n), f(idx + 1, 1, prices, dp, cap, n)); } return profit;}int maxtwobuysell(int prices[], int n){ vector<vector<vector<int> > > dp( n, vector<vector<int> >(2, vector<int>(3, -1))); return f(0, 0, prices, dp, 2, n);}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.*;public class Main { public static int f(int idx, int buy, int[] prices, ArrayList<ArrayList<ArrayList<Integer> > > dp, int cap, int n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } if (dp.get(idx).get(buy).get(cap) != -1) { return dp.get(idx).get(buy).get(cap); } int profit = 0; // you can either buy or not buy if (buy == 0) { dp.get(idx).get(buy).set( cap, profit = Math.max( -prices[idx] + f(idx + 1, 1, prices, dp, cap, n), f(idx + 1, 0, prices, dp, cap, n))); } // you can either sell or not sell else { dp.get(idx).get(buy).set( cap, profit = Math.max( prices[idx] + f(idx + 1, 0, prices, dp, cap - 1, n), f(idx + 1, 1, prices, dp, cap, n))); } return profit; } public static int maxtwobuysell(int[] prices, int n) { ArrayList<ArrayList<ArrayList<Integer> > > dp = new ArrayList<>(n); for (int i = 0; i < n; i++) { dp.add(new ArrayList<>(2)); for (int j = 0; j < 2; j++) { dp.get(i).add(new ArrayList<>(3)); for (int k = 0; k < 3; k++) { dp.get(i).get(j).add(-1); } } } return f(0, 0, prices, dp, 2, n); } public static void main(String[] args) { int[] arr = { 2, 30, 15, 10, 8, 25, 80 }; int size = arr.length; System.out.println(maxtwobuysell(arr, size)); }} |
Python3
# Python program for the above approachimport sysdef f(idx, buy, prices, dp, cap, n): if cap == 0: return 0 if idx == n: return 0 if dp[idx][buy][cap] != -1: return dp[idx][buy][cap] profit = 0 # you can either buy or not buy if buy == 0: dp[idx][buy][cap] = profit = max(-prices[idx] + f(idx + 1, 1, prices, dp, cap, n), f(idx + 1, 0, prices, dp, cap, n)) # you can either sell or not sell else: dp[idx][buy][cap] = profit = max(prices[idx] + f(idx + 1, 0, prices, dp, cap - 1, n), f(idx + 1, 1, prices, dp, cap, n)) return profitdef maxtwobuysell(prices, n): dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n)] return f(0, 0, prices, dp, 2, n)if __name__ == "__main__": arr = [2, 30, 15, 10, 8, 25, 80] size = len(arr) print(maxtwobuysell(arr, size))# This code is contributed by rishabmalhdjio |
Javascript
// JavaScript implementationfunction f(idx, buy, prices, dp, cap, n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } if (dp[idx][buy][cap] != -1) { return dp[idx][buy][cap]; } let profit = 0; // you can either buy or not buy if (buy == 0) { dp[idx][buy][cap] = profit = Math.max(-prices[idx] + f(idx + 1, 1, prices, dp, cap, n), f(idx + 1, 0, prices, dp, cap, n)); } else { // you can either sell or not sell dp[idx][buy][cap] = profit = Math.max(prices[idx] + f(idx + 1, 0, prices, dp, cap - 1, n), f(idx + 1, 1, prices, dp, cap, n)); } return profit;}function maxtwobuysell(prices, n) { const dp = Array.from(Array(n), () => Array.from(Array(2), () => Array(3).fill(-1))); return f(0, 0, prices, dp, 2, n);}const arr = [2, 30, 15, 10, 8, 25, 80];const size = arr.length;console.log(maxtwobuysell(arr, size)); |
C#
using System;class MainClass { static int f(int idx, int buy, int[] prices, int[][][] dp, int cap, int n) { if (cap == 0) { return 0; } if (idx == n) { return 0; } if (dp[idx][buy][cap] != -1) { return dp[idx][buy][cap]; } int profit = 0; // you can either buy or not buy if (buy == 0) { dp[idx][buy][cap] = profit = Math.Max(-prices[idx] + f(idx + 1, 1, prices, dp, cap, n), f(idx + 1, 0, prices, dp, cap, n)); } // you can either sell or not sell else { dp[idx][buy][cap] = profit = Math.Max( prices[idx] + f(idx + 1, 0, prices, dp, cap - 1, n), f(idx + 1, 1, prices, dp, cap, n)); } return profit; } static int maxtwobuysell(int[] prices, int n) { int[][][] dp = new int[n][][]; for (int i = 0; i < n; i++) { dp[i] = new int[2][]; for (int j = 0; j < 2; j++) { dp[i][j] = new int[3]; for (int k = 0; k < 3; k++) { dp[i][j][k] = -1; } } } return f(0, 0, prices, dp, 2, n); } public static void Main() { int[] arr = { 2, 30, 15, 10, 8, 25, 80 }; int size = arr.Length; Console.WriteLine(maxtwobuysell(arr, size)); }}// This code is contributed by divyansh2212 |
Output
100
Time Complexity : O(N)
Auxiliary Space : O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
