TheAlgorithms · Nairit11 · Oct 2, 2019
@@ -0,0 +1,135 @@
+package DynamicProgramming;
+
+import java.util.Deque;
+import java.util.LinkedList;
+
+
+public class StockBuySellKTransactions {
+
+    public int maxProfitLinearSpace(int k, int[] prices) {
+        if (k == 0 || prices.length == 0) {
+            return 0;
+        }
+
+        if (k >= prices.length) {
+            return allTimeProfit(prices);
+        }
+        int[] T = new int[prices.length];
+        int[] prev = new int[prices.length];
+        for (int i = 1; i <= k; i++) {
+            int maxDiff = -prices[0];
+            for (int j = 1; j < prices.length; j++) {
+                T[j] = Math.max(T[j - 1], maxDiff + prices[j]);
+                maxDiff = Math.max(maxDiff, prev[j] - prices[j]);
+            }
+            for (int j = 1; j < prices.length; j++) {
+                prev[j] = T[j];
+            }
+        }
+        return T[T.length - 1];
+    }
+
+    public int allTimeProfit(int arr[]){
+        int profit = 0;
+        int localMin = arr[0];
+        for(int i=1; i < arr.length;i++){
+            if(arr[i-1] >= arr[i]){
+                localMin = arr[i];
+            }else{
+                profit += arr[i] - localMin;
+                localMin = arr[i];
+            }
+
+        }
+        return profit;
+    }
+
+    /**
+     * This is faster method which does optimization on slower method
+     * Time complexity here is O(K * number of days)
+     *
+     * Formula is
+     * T[i][j] = max(T[i][j-1], prices[j] + maxDiff)
+     * maxDiff = max(maxDiff, T[i-1][j] - prices[j])
+     */
+    public int maxProfit(int prices[], int K) {
+        if (K == 0 || prices.length == 0) {
+            return 0;
+        }
+        int T[][] = new int[K+1][prices.length];
+
+        for (int i = 1; i < T.length; i++) {
+            int maxDiff = -prices[0];
+            for (int j = 1; j < T[0].length; j++) {
+                T[i][j] = Math.max(T[i][j-1], prices[j] + maxDiff);
+                maxDiff = Math.max(maxDiff, T[i-1][j] - prices[j]);
+            }
+        }
+        printActualSolution(T, prices);
+        return T[K][prices.length-1];
+    }
+
+    /**
+     * This is slow method but easier to understand.
+     * Time complexity is O(k * number of days ^ 2)
+     * T[i][j] = max(T[i][j-1], max(prices[j] - prices[m] + T[i-1][m])) where m is 0...j-1
+     */
+    public int maxProfitSlowSolution(int prices[], int K) {
+        if (K == 0 || prices.length == 0) {
+            return 0;
+        }
+        int T[][] = new int[K+1][prices.length];
+
+        for (int i = 1; i < T.length; i++) {
+            for (int j = 1; j < T[0].length; j++) {
+                int maxVal = 0;
+                for (int m = 0; m < j; m++) {
+                    maxVal = Math.max(maxVal, prices[j] - prices[m] + T[i-1][m]);
+                }
+                T[i][j] = Math.max(T[i][j-1], maxVal);
+            }
+        }
+        printActualSolution(T, prices);
+        return T[K][prices.length - 1];
+    }
+
+    public void printActualSolution(int T[][], int prices[]) {
+        int i = T.length - 1;
+        int j = T[0].length - 1;
+
+        Deque<Integer> stack = new LinkedList<>();
+        while(true) {
+            if(i == 0 || j == 0) {
+                break;
+            }
+            if (T[i][j] == T[i][j-1]) {
+                j = j - 1;
+            } else {
+                stack.addFirst(j);
+                int maxDiff = T[i][j] - prices[j];
+                for (int k = j-1; k >= 0; k--) {
+                    if (T[i-1][k] - prices[k] == maxDiff) {
+                        i = i - 1;
+                        j = k;
+                        stack.addFirst(j);
+                        break;
+                    }
+                }
+            }
+        }
+
+        while(!stack.isEmpty()) {
+            System.out.println("Buy at price " + prices[stack.pollFirst()]);
+            System.out.println("Sell at price " + prices[stack.pollFirst()]);
+        }
+
+    }
+
+    public static void main(String args[]) {
+        StockBuySellKTransactions sbt = new StockBuySellKTransactions();
+        int prices[] = {2, 5, 7, 1, 4, 3, 1, 3};
+
+        System.out.println("Max profit fast solution " + sbt.maxProfit(prices, 3));
+        System.out.println("Max profit slow solution " + sbt.maxProfitSlowSolution(prices, 3));
+    }
+}