123. Best Time to Buy and Sell Stock III.md

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

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

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

• Approach 1: This is an easy approach but its very slow and space consuming.So here at each max we are storing max price by doing jth transaction we can get. price[j] is current selling price. price[k] is buying price and dp[i-1][k] is profit gained in last transaction upto buying price.

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
        int[][]dp=new int[3][prices.length];
        for(int i=1;i<3;i++){
            for(int j=1;j<prices.length;j++){
                int max=Integer.MIN_VALUE;
                for(int k=0;k<j;k++){
                    max=Math.max(prices[j]-prices[k]+dp[i-1][k],max);
                }
                dp[i][j]=Math.max(dp[i][j-1],max);
            }
        }
        
        return dp[2][prices.length-1];
    }
}

• A much better approach that will reduce the time complexity from O(nn2) to O(n*2) or just o(N) by replacing the

max=Math.max(prices[j]-prices[k]+dp[i-1][k],max);

with max profit so far in last transaction - price of buying because when we write the equations for every cell calculation then we will see out last loop is useless.

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
        int[][]dp=new int[3][prices.length];
        for(int i=1;i<3;i++){
            int maxTillNow=Integer.MIN_VALUE;
            for(int j=1;j<prices.length;j++){
                maxTillNow=Math.max(maxTillNow,dp[i-1][j-1]-prices[j-1]);
                dp[i][j]=Math.max(dp[i][j-1],maxTillNow+prices[j]);
            }
        }
        return dp[2][prices.length-1];
    }
}

• Best solution for this problem would be the following as it reduces space complexity from O(N*N) to O(N) as we are not using 2d array now . We just access to want previous transaction to keep track of profit till the buying day.So we take two arrays and use one as current array and one as current array so we make changes in current array using previous array then in next transaction we use current array as previous transaction array.

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
        int[] oddProfits=new int[prices.length];
        int[] evenProfits=new int[prices.length];
        for(int i=1;i<3;i++){
            int maxTillNow=Integer.MIN_VALUE;
            int[] current=new int[prices.length];
            int[] previousProfit=new int[prices.length];
            if(i%2==1){
                current=oddProfits;
                previousProfit=evenProfits;
            }
            else{
                current=evenProfits;
                previousProfit=oddProfits;
            }
            for(int j=1;j<prices.length;j++){
                maxTillNow=Math.max(maxTillNow,previousProfit[j-1]-prices[j-1]);
                current[j]=Math.max(current[j-1],maxTillNow+prices[j]);
            }
        }
        return evenProfits[prices.length-1];
    }
}