Sort an array of 0s, 1s or 2-way Partitioning

/*
 * Sort an array of 0s, 1s
 * reference: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
 */
public class Partition2Way {
    int numArr[] = null;
   
    public Partition2Way(){
        numArr = null;
    }
   
    public Partition2Way(int n){
        numArr = new int[n];
    }
   
    public void sort2Way(int a[]){
        int low = 0;
        int mid = 0;
        int high = a.length-1;
        while(mid <= high){
            switch(a[mid]){
                case 0:
                    int t = a[low];
                    a[low] = a[mid];
                    a[mid] = t;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
            }
        }
        this.numArr = a;
    }
   
    public void printArr(int a[]){
        System.out.print("Sorted List: ");
        for(int i=0; i<a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
   
    public static void main(String args[]){
        int a[] = {0,1,1,1,0,0,1,1,0,1};
        Partition2Way pw = new Partition2Way(a.length);
        pw.sort2Way(a);
        pw.printArr(pw.numArr);
    }
}

#output:

Sorted List: 0 0 0 0 1 1 1 1 1 1 

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

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)