123. Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example: 1

Input: prices = [3,3,5,0,0,3,1,4]

Output: 6

Example: 2

Input: [1,2,3,4,5]

Output: 4

Example: 3

Input: [7,6,4,3,1]

Output: 0

Example: 4

Input: [1]

Output: 0

Constraints:

• 1 <= prices.length <= 10 ^ 5
• 0 <= prices[i] <= 10 ^ 5

Solving the whole problem using recursion:

• The pattern of buying and selling can be denoted as BS or BSBS, where B stands for buy and S stands for sell.
• So we will define a variable called condition in our recursion. If this variable condition is even then we can buy the current element at idx. If this variable is odd then we can sell the current element at idx.
• So at each step we will either use the current element according to our condition or ignore it and go to the next element.
• The recursive program for this is shown below.

Code using recursion (TLE): class Solution { public int maxProfit(int[] prices) { long ans = recur(0, 0, prices); ans = Math.max(ans, 0); return (int) ans; } long recur(int idx, int condition, int[] prices) { // if we have made two successful transactions // then we cannot make other transactions // so we will return 0 if(condition == 4) return 0; // failure conditions // if we have bought a stock // and we are already at last index // then we return Integer.MIN_VALUE // because there is no way to sell what we have bought now if(idx == prices.length - 1 && condition % 2 == 0) return Integer.MIN_VALUE; // since we have checked for failure condition above // now, all incomplete transactions will be filtered // so in this step if we are at last index of array // we will simply return that element... because it will be idx where we will sell the stock if(idx == prices.length - 1) return prices[idx]; // if condition is even = buy -> -price // if condition is odd = sell -> +price int curCost = (condition % 2 == 0) ? -prices[idx] : prices[idx]; // there are two ways to follow... // either ignore the current element // or, take this element and switch from buy to sell or sell to buy and then go to next element long ans = Math.max(recur(idx + 1, condition, prices), curCost + recur(idx + 1, condition + 1, prices)); // sometimes we will only be able to make one transaction // so we are checking for that condition here // that if we terminated our first transaction here at idx if(condition == 1) { ans = Math.max(ans, prices[idx]); } return ans; } }

Caching the subproblems (TLE to Accepted):

• Now the above code gives TLE.
• This is because we are computing subproblems again and again.
• So we will just cache the subproblems for idx and condition values. This will get us accepted :)

Code using DP: class Solution { // initializing memo array Integer[][] dp; public int maxProfit(int[] prices) { dp = new Integer[prices.length][5]; long ans = recur(0, 0, prices); ans = Math.max(ans, 0); return (int) ans; } int recur(int idx, int condition, int[] prices) { if(condition == 4) return 0; if(idx == prices.length - 1 && condition % 2 == 0) return -1000000; if(idx == prices.length - 1) return prices[idx]; // checking if we have already solved this subproblem // if yes return its value if(dp[idx][condition] != null) { return dp[idx][condition]; } int curCost = (condition % 2 == 0) ? -prices[idx] : prices[idx]; // storing optimal result for the current subproblem // so that it can be used later on dp[idx][condition] = Math.max(recur(idx + 1, condition, prices), curCost + recur(idx + 1, condition + 1, prices)); // checking for condition where, we terminate our transaction at idx // and make no further transactions if(condition == 1) { dp[idx][condition] = Math.max(dp[idx][condition], prices[idx]); } return dp[idx][condition]; } }