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)