DP

package testrun;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class DynamicProgrammingProblem {

    public static ArrayList<Integer[]> diskStacking(ArrayList<Integer[]> disks) {
        ArrayList<Integer[]> retList = new ArrayList<Integer[]>();
        // sort disk List by height
        disks.sort((d1, d2) -> d1[2].compareTo(d2[2]));
        // heights array to store max height upto that index;
        int[] heights = new int[disks.size()];
        for (int i = 0; i < disks.size(); i++) {
            heights[i] = disks.get(i)[2];
        }
        // sequence array to manintain the last max height index for each entry
        int[] seq = new int[disks.size()];
        Arrays.fill(seq, Integer.MIN_VALUE);

        // maintain the index for index at max height

        int maxHeighIndex = 0;
        for (int i = 1; i < disks.size(); i++) {
            Integer[] currentDisk = disks.get(i);
            for (int j = 0; j < i; j++) {
                Integer[] otherDisk = disks.get(j);
                // check all valid dimensions
                if (otherDisk[0] < currentDisk[0] && otherDisk[1] < currentDisk[1] && otherDisk[2] < currentDisk[2]) {
                    if (heights[i] < heights[j] + currentDisk[2]) {
                        heights[i] = heights[j] + currentDisk[2];
                        seq[i] = j;
                    }
                }
            }
            if (heights[i] > heights[maxHeighIndex]) {
                maxHeighIndex = i;
            }
        }
        while (maxHeighIndex != Integer.MIN_VALUE) {
            retList.add(0, disks.get(maxHeighIndex));
            maxHeighIndex = seq[maxHeighIndex];
        }
        System.out.print(retList);
        return retList;
    }

    public static ArrayList<ArrayList<Integer>> knapsackProblem(int[][] items, int capacity) {
        ArrayList<ArrayList<Integer>> returnList = new ArrayList<ArrayList<Integer>>();
        if (capacity <= 0) {
            ArrayList<Integer> l = new ArrayList<Integer>();
            l.add(0);
            returnList.add(l);
            returnList.add(new ArrayList<Integer>());
            return returnList;
        }

        int n = items.length + 1;
        int dpMat[][] = new int[n][capacity + 1];

        for (int i = 1; i < n; i++) {
            int curItem = items[i - 1][0];
            int curWeight = items[i - 1][1];
            for (int j = 0; j <= capacity; j++) {
                if (curWeight <= j) {
                    dpMat[i][j] = Math.max(curItem + dpMat[i - 1][j - curWeight], dpMat[i - 1][j]);
                } else {
                    dpMat[i][j] = dpMat[i - 1][j];
                }
            }
        }

        int weight = dpMat[n - 1][capacity];
        ArrayList<Integer> l = new ArrayList<Integer>();
        l.add(weight);
        returnList.add(l);
        returnList.add(new ArrayList<Integer>());
        int i = dpMat.length - 1;
        int c = dpMat[0].length - 1;
        while (i > 0) {
            if (dpMat[i][c] == dpMat[i - 1][c]) {
                i--;
            } else {
                returnList.get(1).add(0, i - 1);
                c = c - items[i - 1][1];
                i--;

            }
            if (c == 0) {
                break;
            }

        }

        System.out.print(returnList);
        return returnList;
    }

    public static class Box implements Comparable<Box> {
        int l, b, h, area;

        public Box(int l, int b, int h) {
            super();
            this.l = l;
            this.b = b;
            this.h = h;
        }

        @Override
        public int compareTo(Box b) {
            return b.area - this.area;
        }
    }

    public static int getMaxHeightFromBoxStack(Box[] boxes, int n) {
        Box[] sortedBox = new Box[n * 3];
        for (int i = 0; i < n; i++) {
            Box box = boxes[i];
            sortedBox[3 * i] = new Box(box.h, Math.max(box.l, box.b), Math.min(box.l, box.b));
            sortedBox[3 * i + 1] = new Box(box.l, Math.max(box.h, box.b), Math.min(box.h, box.b));
            sortedBox[3 * i + 2] = new Box(box.b, Math.max(box.l, box.h), Math.min(box.l, box.h));
        }
        for (int i = 0; i < sortedBox.length; i++) {
            sortedBox[i].area = sortedBox[i].l * sortedBox[i].b;
        }
        Arrays.sort(sortedBox);
        int count = 3 * n;
        int[] msh = new int[count];
        for (int i = 0; i < count; i++) {
            msh[i] = sortedBox[i].h;
        }

        for (int i = 1; i < n; i++) {
            msh[i] = 0;
            Box box = sortedBox[i];
            int val = 0;
            for (int j = 0; j < i; j++) {
                Box prevBox = sortedBox[j];
                if (box.l < prevBox.l && box.b < prevBox.b) {
                    val = Math.max(val, msh[j]);
                }
            }
            msh[i] = val + box.h;
        }
        int max = -1;

        /* Pick maximum of all msh values */
        for (int i = 0; i < count; i++) {
            max = Math.max(max, msh[i]);
        }

        return max;
    }

    public static ArrayList<ArrayList<Integer>> maxSumIncreasingSubsequence(int[] array) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        int sequenceOfMaxSum[] = new int[array.length];
        Arrays.fill(sequenceOfMaxSum, Integer.MIN_VALUE);
        int sum[] = new int[array.length];
        sum = array.clone();
        int maxSumIndex = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[i] > array[j] && sum[j] + array[i] >= sum[i]) {
                    sum[i] = sum[j] + array[i];
                    sequenceOfMaxSum[i] = j;
                }
            }
            if (sum[i] > sum[maxSumIndex]) {
                maxSumIndex = i;
            }
        }

        list.add(new ArrayList<Integer>());
        list.add(new ArrayList<Integer>());
        list.get(0).add(sum[maxSumIndex]);
        while (maxSumIndex != Integer.MIN_VALUE) {
            list.get(1).add(0, array[maxSumIndex]);
            maxSumIndex = sequenceOfMaxSum[maxSumIndex];
        }

        // System.out.print(list);
        return list;
    }

    public static int minNumberOfJumps(int[] arr) {
        if (arr.length <= 1)
            return 0;

        // Return -1 if not possible to jump
        if (arr[0] == 0)
            return -1;

        // initialization
        int maxReach = arr[0];
        int step = arr[0];
        int jump = 1;

        // Start traversing array
        for (int i = 1; i < arr.length; i++) {
            // Check if we have reached the end of the array
            if (i == arr.length - 1)
                return jump;

            // updating maxReach
            maxReach = Math.max(maxReach, i + arr[i]);

            // we use a step to get to the current index
            step--;

            // If no further steps left
            if (step == 0) {
                // we must have used a jump
                jump++;

                // Check if the current index/position or lesser index
                // is the maximum reach point from the previous indexes
                if (i >= maxReach)
                    return -1;

                // re-initialize the steps to the amount
                // of steps to reach maxReach from position i.
                step = maxReach - i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // int n = getFibonacciNo(4);
        // System.out.print("Fabonacci " + n);
        // coinChangeProblem();
        // largestRectangleArea();
        // longestCommonSubsequence("ABCDEFG", "APPLES");
        // int[] input = { 8, 12, 2, 3, 15, 5, 7 };
        // maxSumIncreasingSubsequence(input);
        // int[][] input = { { 1, 2 }, { 4, 3 }, { 5, 6 }, { 6, 7 } };
        // knapsackProblem(input, 10);

        ArrayList<Integer[]> input = new ArrayList<Integer[]>();
        input.add(new Integer[] { 2, 1, 2 });
        input.add(new Integer[] { 3, 2, 3 });
        input.add(new Integer[] { 2, 2, 8 });
        input.add(new Integer[] { 2, 3, 4 });
        input.add(new Integer[] { 2, 2, 1 });
        input.add(new Integer[] { 4, 4, 5 });
        diskStacking(input);
    }

    public static int getFibonacciNo(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int f[] = new int[n + 2];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }

    // https://www.geeksforgeeks.org/gold-mine-problem/
    public static void goldMineProblem() {
        int goldMine[][] = { { 1, 3, 1, 5 }, { 2, 2, 4, 1 }, { 5, 0, 2, 3 }, { 0, 6, 1, 2 } };
        int m = 4, n = 4;
        int minerTable[][] = new int[m][n];
        for (int[] rows : minerTable) {
            Arrays.fill(rows, 0);
        }
        for (int column = n - 1; column >= 0; column--) {
            for (int row = 0; row < m; row++) {
                // gold collected at right move,If at last column gold collected
                // will be zero,other wise it will be same row next column
                int rightCost = (column == n - 1) ? 0 : minerTable[row][column + 1];
                // gold collected at right up,If first row or last column gold
                // collected will be zero.other wise previous row,next column
                int rightUpwords = (row == 0 || column == n - 1) ? 0 : minerTable[row - 1][column + 1];
                // gold collected at right up,If last row or last column gold
                // collected will be zero.other wise next row,next column
                int rightDown = (row == m - 1 || column == n - 1) ? 0 : minerTable[row + 1][column + 1];
                // Max gold collected from taking
                // either of the above 3 paths
                minerTable[row][column] += goldMine[row][column]
                        + Math.max(rightCost, Math.max(rightUpwords, rightDown));
            }
        }
        // The max amount of gold collected will be
        // the max value in first column of all rows
        int maxGoldCollected = minerTable[0][0];
        for (int i = 1; i < m; i++) {
            maxGoldCollected = Math.max(maxGoldCollected, minerTable[i][0]);
        }
        System.out.println("Max gold collected by minor: " + maxGoldCollected);
    }

    public static void coinChangeProblem() {
        int coins[] = { 1, 2, 3 };
        int amount = 5;
        int noOfWays[][] = new int[coins.length + 1][amount + 1];

        // if amount=0 then just return empty set to make the change
        for (int val = 0; val < coins.length; val++) {
            noOfWays[val][0] = 1;
        }
        // if no coins given, 0 ways to make the amount
        for (int i = 1; i <= amount; i++) {
            noOfWays[0][i] = 0;

        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                // check if the coin value is less than the amount needed
                if (coins[i - 1] <= j) {
                    // reduce the amount by coin value and
                    // use the subproblem solution (amount-v[i]) and
                    // add the solution from the top to it
                    noOfWays[i][j] = noOfWays[i][j - coins[i - 1]] + noOfWays[i - 1][j];
                } else {
                    // just copy the value from the top
                    noOfWays[i][j] = noOfWays[i - 1][j];
                }
            }
        }
        System.out.print("No OF ways:" + noOfWays[coins.length][amount]);

        // o(n) space solution

        int table[] = new int[amount + 1];
        table[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                table[j] += table[j - coins[i]];
            }
        }
        System.out.print("No OF ways:" + table[amount]);

    }

    // https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

    public static void cutRodProblem(int price[], int n) {
        int cost[] = new int[n + 1];
        cost[0] = 0;

        for (int i = 1; i < n; i++) {
            int maxVal = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                maxVal = Math.max(maxVal, price[j] + cost[i - j - 1]);
                cost[i] = maxVal;
            }
        }
        System.out.print("MAx value for cutting rod: " + cost[n]);
    }

    public static int largestIncreasingSeqRecursion(int[] arr, int startingindex, int length, int previousELelment) {
        if (arr == null || length == 0 || startingindex == length) {
            return 0;
        }
        int exclude = largestIncreasingSeqRecursion(arr, startingindex + 1, length, previousELelment);
        int include = 0;
        if (arr[startingindex] > previousELelment) {
            include = 1 + largestIncreasingSeqRecursion(arr, startingindex + 1, length, arr[startingindex]);

        }
        return Math.max(exclude, include);
    }

    public static int LISWithMaxSum(int[] arr) {
        int length = arr.length;
        int[] dp = new int[length];

        for (int i = 0; i < dp.length; i++) {
            dp[i] = arr[i];
        }

        // start from second
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                // if current element is greater than previous and sequence end
                // at arr[j]
                if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i]) {
                    dp[i] = dp[j] + arr[i];
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();

    }

    public static int LISWithDP(int[] arr) {
        int length = arr.length;
        int[] dp = new int[length];
        // if include current element in sequence
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        // start from second
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                // if current element is greater than previous and sequence end
                // at arr[j]
                if (arr[i] > arr[j] && dp[i] < dp[j]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static ArrayList<Character> longestCommonSubsequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] mat = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    mat[i][j] = 0;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    mat[i][j] = mat[i - 1][j - 1] + 1;
                } else {
                    mat[i][j] = Math.max(mat[i - 1][j], mat[i][j - 1]);
                }

            }
        }

        ArrayList<Character> list = new ArrayList<Character>();

        int i = m;
        int j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                list.add(0, str1.charAt(i - 1));
                i--;
                j--;

            } else if (mat[i - 1][j] > mat[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return list;
    }

    public static int largestRectangleArea() {
        int height[] = { 1, 2, 3, 4, 5, 2, 7 };
        if (height == null || height.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int i = 0;

        while (i < height.length) {
            // push index to stack when the current height is larger than the
            // previous one
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
                System.out.println("Stack status in first loop: " + stack.toString());
            } else {
                // calculate max value when the current height is less than the
                // previous one
                int p = stack.pop();
                int h = height[p];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(h * w, max);

                System.out.println("Stack status in sencond loop: " + stack.toString());
                System.out.println("Max Area so far: " + max);

            }
        }
        while (!stack.isEmpty()) {
            int p = stack.pop();
            int h = height[p];
            int w = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(h * w, max);
        }

        System.out.print("Max Area: " + max);
        return max;
    }
}