Buy and Sell stocks twice

Question

I am working on understanding this problem where I need to find out the max profit when I am allowed to buy/sell stocks at most twice. The provided solution talks about maintaining price difference array from left to right and that makes sense to me. However the post also talks about maintaining another array of price difference from right to left and I am not able to understand that logic as why does that gives profit after the first transaction.

Prices= [1, 4, 5, 7, 6, 3, 2, 9]
left  = [0, 3, 4, 6, 6, 6, 6, 8]
right = [8, 7, 7, 7, 7, 7, 7, 0]
max_profit = 13

Answer 1

The fact that there are two arrays in the proposed solution that you mentioned is related to the constraint of the problem that allows using only 2 transactions.

As also specified, the transactions should not be intercalated -- i.e. one transaction should be before (to the left of) the other one (which will be to the right).

More specifically, the two arrays in the proposed solution represent the following:

• left[i] = the best transaction that can be made by buying and selling in the interval [0, i]. If selling is done at time j (with j in [0, i]), the buy should be done at the minimum price from 0 to j.

• right[i] = the best transaction that can be made by buying and selling in the interval [i, n-1]. If buying is done at time j (with j in [i, n-1]), the selling should be done at the maximum price from j to n-1.

All that needs to be found is a good separation point, i, of the two transactions. Then the best combination will involve the profit left[i] + right[i], and this can be found by trying all possible i values.

Answer 2

You can break the problem as DP, make first set case where you are not buying and selling the stocks so the first profit will be zero, make the profit in same sequence

When only one transaction is made

Track the array and maintain the minimum of the number with previous price the max profit is max number - min number in the array. so problem is basically finding max and min in an array and difference will be the maximum profit, here we just updating the profit array as to what is maximum profit till that particular day is transaction in made or not. This array will be used as the usage of data in the further transaction is asked.

// Condition for the only one transaction is possible
       for (int i = 1; i < n; i++) {
         min = Math.min(price[i - 1], min);
           profit[i] = Math.max(profit[i - 1], price[i] - min);
        }

If at most two transaction can be made

Now here the thing is tricky, we have to just keep the track of any previous computations made for the max profit made till that dat for k-1 transaction (here k=2). The problem can be made a dynamic problem for any number of the transactions.

profit for a particular day is = max{ if no transaction is made (Then previous max profit, ie profit[i - 1]),
previous_profit + Max of sale possible{present price - all previous price(i,i-1,...0)) 

For k=2

//   Condition for at most two transaction is possible
        for (int i = 1; i < n; i++) {
           max = Math.max(max, profit[i] - price[i]);
             profit[i] = Math.max(profit[i - 1], max + price[i]);
        }

Here is general code for k transactions We just need two array to track the previous profit value and override on each iteration. It can also be done using 2-D array still we don't need any previous data so I made it with even and positive data array

   package DynamicProblems;

    public class StockSales {

        private static int maxProfit(int price[], int n, int k) {
            int currentProfit[] = new int[n];
            int previousProfit[];
            int evenProfit[] = new int[n];
            int oddProfit[] = new int[n];

            for (int t = 0; t <= k - 1; t++) {
                int max = Integer.MIN_VALUE;
                if (t % 2 == 1) {
                    currentProfit = oddProfit;
                    previousProfit = evenProfit;
                } else {
                    currentProfit = evenProfit;
                    previousProfit = oddProfit;
                }

                for (int i = 1; i < n; i++) {
                    max = Math.max(max, previousProfit[i - 1] - price[i - 1]);
                    currentProfit[i] = Math.max(currentProfit[i - 1], max + price[i]);
                }
            }
            return currentProfit[n - 1];
        }

        public static void main(String args[]) {
            int price[] = {3, 4, 10, 103};
            int k = 1;
            int n = price.length;
            System.out.println("\nMaximum Profit = " + maxProfit(price, n, k));
        }
    }