Dynamic Programming Question: maximize profit for wine sale

/**
 * you have a collection of N wines placed next to each other on a shelf. For
 * simplicity, let's number the wines from left to right as they are standing on
 * the shelf with integers from 1 to N, respectively. The price of the i-th wine
 * is pi (prices of different wines can be different).
 * Because the wines get better every year, supposing today is the year 1, on
 * year y the price of the i-th wine will be y*pi, i.e. y-times more than the
 * current year.
 * what is the maximum profit you can get, if you sell the wines in optimal order.
 * So for example, if the prices of the wines are (in the order as they are
 * placed on the shelf, from left to right): p1=1, p2=4, p3=2, p4=3.
 *
 */
public class DP1 {
    int p[] = null;
    int cache[][];
   
    public DP1(){
        p = new int[100];
        cache = new int[100][100];
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++)
                cache[i][j] = -1;
    }
   
    public DP1(int N){
        p = new int[N];
        cache = new int[N][N];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                cache[i][j] = -1;
    }
   
    /**
     * Description: Backtracking function to find maximum profit.
     * @param year : starts from 1 to N-1
     * @param be : beginning of price array
     * @param en : end of price array
     * @return : maximized profit
     */
    public int maxProfit(int year, int be, int en){
        if(be>en)
            return 0;
        return Math.max((this.maxProfit(year+1, be+1, en)+year*this.p[be]),(this.maxProfit(year+1, be, en-1) + year*p[en]));
    }
   
    /*
     * Dynamic Programming Approach
     */
    public int maxDPProfit(int be, int en){
        if(be > en)
            return 0;
       
        if(cache[be][en] != -1)
            return cache[be][en];
       
        int year = this.p.length - (en-be+1) + 1;
        cache[be][en] = Math.max((this.maxDPProfit(be+1, en) + year*p[be]),(this.maxDPProfit(be, en-1)+year*p[en]));
        return cache[be][en];
    }
   
    public static void main(String args[]){
        DP1 dp = new DP1();
        int p[] = new int[]{1,4,2,3};
        dp.p = p;
        int profit = dp.maxProfit(1, 0, 3);
        System.out.println("Profit: " + profit);
        //DP
        int dpprofit = dp.maxDPProfit(0, 3);
        System.out.println("DP Profit: " + dpprofit);
    }
}

#output:

Profit: 29

DP Profit: 29

Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0

/**
   * Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
   * e.g. Let A = -1 0 9 5 -5 2 3
   * Answer = {0 5 -5} {-5 2 3}.
   * Expected : Time O(n2) Space O(1)
 */
public class Prob3Sum {

    public void find3Sum(int A[]){
        for(int i=0; i<A.length; i++){
            int l = i+1;
            int r = A.length - 1;
            while(l<r){
                if(A[i] + A[l] + A[r] == 0){
                    System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
                }
                if(A[i] + A[l] + A[r] > 0)
                    r--;
                else
                    l++;
            }
        }
    }
   
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
        sort.quickSort(sort.A, 0, sort.A.length-1);
        sort.printArr();
       
        Prob3Sum ps = new Prob3Sum();
        ps.find3Sum(sort.A);
       
    }
}

#output

Sorted: -5, -1, 0, 2, 3, 5, 9, 

Sum: -5 0 5

Sum: -5 2 3

Level Order Traversal for Binary Tree

    public void levelTraversal(TNode root) {
        TNodeQueue queue = new TNodeQueue();
        if(root != null){
            queue.push(root);
            while(!queue.isEmpty()){
                //System.out.println("Queue: " + queue.isEmpty());
                TNode tmp = queue.pop();
                System.out.print(tmp.data + " ");
                if(tmp.left != null)
                    queue.push(tmp.left);
                if(tmp.right != null)
                    queue.push(tmp.right);
            }
        }
    }

# output

Inorder:

2 4 6 8 9 10 

Level Order Traversal: 

8 4 9 2 6 10 

Stack with TNode (Tree Node)

public class NodeStack {

    TNode stack[] = null;
    int top = 0;

    //int ssize = 0;
    NodeStack(int n) {
        stack = new TNode[n];
    }

    NodeStack() {
        stack = new TNode[100];
    }

    public boolean isEmpty() {
        if (top < 0) {
            return true;
        } else {
            return false;
        }
    }

    public void printPop() {
        System.out.println("Poppoed " + this.pop().data);
    }

    public void push(TNode p) {
        if (top < stack.length) {
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }

    public TNode top(){
        if(top>0)
            return stack[top-1];
        return null;
    }
    public TNode pop() {
        TNode p = null;
        if (top > 0) {
            p = stack[--top];
        }
        //System.out.println("Top: " + top);
        return p;
    }

    public void printStack() {
        System.out.print("Stack [LIFO order]: ");
        for (int i = this.top - 1; i >= 0; i--) {
            System.out.print(stack[i].data + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        NodeStack s = new NodeStack();
        s.push(new TNode(10));
        s.push(new TNode(15));
        s.push(new TNode(20));
        s.push(new TNode(25));
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(new TNode(19));
        s.push(new TNode(24));
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
}

# output:

Stack [LIFO order]: 25 20 15 10 

Poppoed 25

Poppoed 20

Stack [LIFO order]: 24 19 15 10 

Poppoed 24

Poppoed 19

Poppoed 15

Poppoed 10

Stack [LIFO order]: 

Iterative or non-recursive version of Binary Tree Inorder, Preorder & Postorder

 public void nonRecursiveInorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            System.out.print(root.data + " ");
            root = root.right;
        }
    }

    public void nonRecursivePreorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                System.out.print(root.data + " ");
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            root = root.right;
        }
    }

    public void nonRecursivePostorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while(root != null){
                if(root.right != null)
                    s.push(root.right);
                s.push(root);
                root = root.left;
            }
            if(s.isEmpty())
                break;
            root = s.pop();
            if(root == null)
                break;
            if(root.right != null && s.top() == root.right){
                s.pop();
                s.push(root);
                root = root.right;
            }else{
                System.out.print(root.data + " ");
                root = null;
            }
        }
    }

[Reference: http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/]

For TNode definition, please check my previous post.

Largest Sum Contiguous Subarray..

Reference: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

public class MaxSubArray {

    /*
    Notes: Algorithm doesn't work for all negative numbers. It simply returns 0
    if all numbers are negative. For handling this we can add an extra phase
    before actual implementation. The phase will look if all numbers are negative,
    if they are it will return maximum of them (or smallest in terms of absolute
    value). There may be other ways to handle it though.
    */
    public int findMaxSubArray(int a[]){
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i=0; i<a.length; i++){
            max_ending_here += a[i];
            if(max_ending_here < 0)
                max_ending_here = 0;
            if(max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
 
    /*
     * Another implementation which takes care of all +ve as well as -ve value.
     */
    public int findMaxSubArray2(int a[]){
        int max_so_far = a[0];
        int current_max = a[0];
        for(int i=1; i<a.length; i++){
            current_max = Math.max(a[i], current_max+a[i]);
            max_so_far = Math.max(max_so_far, current_max);
        }
        return max_so_far;
    }
 
    public static void main(String args[]){
        MaxSubArray msa = new MaxSubArray();
        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
        int res = msa.findMaxSubArray(a);
        System.out.println("MaxSum: " + res);
        int b[] = {-2, -3, -4, -1, -2, -1, -5, -3};
        res = msa.findMaxSubArray2(b);
        System.out.println("MaxSum2: " + res);
    }
}

# Output

MaxSum: 7

MaxSum2: -1

To divide an array such that the sum of left half and right half is minimum.

/*
Prob: To divide an array such that the sum of left half and right half is minimum or partition an array in equal halves with minimum sum difference.
A = 1,2,3,4,5,6,7,8,9,10 #Array is not sorted
left=1,4,5,8,9,1 (sum=27) right=2,3,6,7,10(sum=28)
Complexity: O(n^2) Type: GREEDY
*/

public class DivideArray {

    int A[];
    boolean used[];
    int partition[];
    int left = 0;
    int right = 0;

    DivideArray() {
        A = null;
        used = null;
        partition = null;
        left = -1;
        right = -1;
    }

    DivideArray(int N) {
        A = new int[N];
        used = new boolean[N];
        partition = new int[N];
        left = 0;
        right = N - 1;
    }

    public int findNearest(int A[], boolean used[], int idx) {
        int min = 99999999;
        int minIndex = -1;
        for (int i = 0; i < A.length; i++) {
            if (i == idx) {
                continue;
            }
            if (used[i]) {
                continue;
            }
            int diff = Math.abs(A[idx] - A[i]);
            if (diff < min) {
                min = diff;
                minIndex = i;
            }
        }
        return minIndex;
    }

    public void partitionArr(int A[], boolean used[], int partition[]) {
        for (int i = 0; i < A.length; i++) {
            if (used[i]) {
                continue;
            }
            int j = findNearest(A, used, i);
            used[i] = true;
            if (j >= 0) {
                used[j] = true;
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = Math.max(A[i], A[j]);
                    partition[right--] = Math.min(A[i], A[j]);
                } else {
                    partition[left++] = Math.min(A[i], A[j]);
                    partition[right--] = Math.max(A[i], A[j]);
                }
            } else {
                // if size of array is odd
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = A[i];
                } else {
                    partition[right--] = A[i];
                }

            }
        }
        this.partition = partition;
    }

    public int sumLeft(int par[], int left) {
        int sum = 0;
        for (int i = 0; i <= left; i++) {
            sum += par[i];
        }
        return sum;
    }

    public int sumRight(int par[], int right) {
        int sum = 0;
        for (int i = right; i < par.length; i++) {
            sum += par[i];
        }
        return sum;
    }

    public static void main(String args[]) {

        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt();
        DivideArray da = new DivideArray(N);

        for (int i = 0; i < N; i++) {
            da.A[i] = sin.nextInt();
        }
        // call partition function
        da.partitionArr(da.A, da.used, da.partition);
        System.out.print("LeftArray: ");
        for (int i = 0; i < da.left; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.print("\t(sum=" + da.sumLeft(da.partition, da.left - 1) + ")\nRightArray: ");
        for (int i = da.right + 1; i < N; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.println("\t(sum=" + da.sumRight(da.partition, da.right + 1) + ")");

    }
}


## Output
10
1 2 3 4 5 6 7 8 9  10
LeftArray: 2 3 6 7 10     (sum=28)
RightArray: 9 8 5 4 1     (sum=27)

9
9
1 2 3 4 5 6 7 8 9
LeftArray: 2 3 6 7 9     (sum=27)
RightArray: 8 5 4 1     (sum=18)

Quick Sort (in java)

public class QuickSort {

    public int A[] = null;

    public int partition(int A[], int low, int high) {
        int left, right, pivot_item = A[low];
        left = low;
        right = high;

        while (left < right) {
       
            while (left < right && A[left] <= pivot_item) {
                left++;
            }
            while (A[right] > pivot_item) {
                right--;
            }

            if (left < right) {
                int temp = A[right];
                A[right] = A[left];
                A[left] = temp;
            }
        }
     
        A[low] = A[right];
        A[right] = pivot_item;
        return right;
    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public void quickSort(int A[], int low, int high) {
        int pivot;
        if (high > low) {
            pivot = partition(A, low, high);
           // System.out.println("Pivot: " + pivot);
            quickSort(A, low, pivot - 1);
            quickSort(A, pivot + 1, high);
        }
       // this.printArr();
    }

    public static void main(String args[]) {
        QuickSort sort = new QuickSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.quickSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

Merge Sort in Java

public class MergeSort {

    public int A[], temp[]; //, size=0;

    MergeSort(int n) {
        A = new int[n];
        temp = new int[n];
        //size = n;
    }

    MergeSort() {
        A = null;
        temp = null;
        //size = 0;
    }

    public void mergeSort(int A[], int left, int right) {
        int mid;
        //System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
        if (left < right) {
            mid = (right + left) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            merge(A, left, mid, right);
        }
    }

    public void merge(int A[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L1[] = new int[n1];
        int L2[] = new int[n2];
     
        for (int i = 0; i < n1; i++) {
            L1[i] = A[left + i];
        }

        for (int i = 0; i < n2; i++) {
            L2[i] = A[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L1[i] <= L2[j]) {
                A[k] = L1[i];
                i++;
            } else {
                A[k] = L2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            A[k] = L1[i];
            i++;
            k++;
        }

        while (j < n2) {
            A[k] = L2[j];
            j++;
            k++;
        }

    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MergeSort sort = new MergeSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.temp = new int[8];
        sort.mergeSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}