Array subset unequal sums

Question

I have a requirement to write a function to divide an array in 2 parts {4,5,2,1,3}, such that sum in first array is greater than in second array but length of 1st array is smaller than that of second.The union of their sums is total sum and they dont have any intersection.So, an answer would be {4,5}.

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

public class DP2 {

    public static void main(String args[]) {
        int[] arr= {5,2,10,4,1,11};
        ArrayList<Integer> list=new ArrayList<>();
        //calculate sum
        int finalSum=0;
        /*
        for(int i: arr)
            finalSum+=arr[i];
            */
        int len=arr.length;
        int mid=(len)/2;
        System.out.println(mid);
        int sum=0;
        //initialize 2 pointers

        //will use a stack
        Stack<Integer> stack = new Stack<Integer>();

        int i=0,j=len-1;
        int max=Integer.MIN_VALUE;
        while(i < j ) {
            //int max=Math.max(arr[i], arr[j]);
        //  System.out.println(max);
            while(stack.size() < mid) {


                max=Math.max(arr[i], arr[j]);
                stack.push(max);
                //System.out.println(stack.size());
            //  System.out.println(stack.peek());
                i++;
                j--;
            }

        //  max=Math.max(arr[i], arr[j]);
            i++;
            j--;

            if(stack.size() < mid  && stack.peek() < max  ) {




                    stack.pop();
                    stack.push(max);


                }




        }


        while(!stack.isEmpty())
            System.out.println(stack.pop());




        }
    }

It wont return the expected answer. It is not popping out from stack as I had coded to do. Can someone please help what I am doing wrong.

Answer 1

From what I can see there is nothing wrong, everything works as expected. The only problem was that the popping operation was giving you the result in reverse order. I have fixed that in the code below:

Integer[] result = new Integer[stack.size()];
for (int i1 = result.length - 1; i1 >= 0 && !stack.isEmpty(); i1--) {
    result[i1] = stack.pop();
}
System.out.println(Arrays.toString(result));

Output [4, 5]

EDIT: As requested here is a full solution to your problem:

/**
 * Convert an array of primitive numbers to Integer objects.
 */
private static Integer[] intToInteger(int[] array) {
    return Arrays.stream(array).boxed().toArray( Integer[]::new );
}

/**
 * Converts a primitive integer array to an ArrayList.
 */
private static ArrayList<Integer> intArrayTolist(int[] array) {
    return new ArrayList<>(Arrays.asList(intToInteger(array)));
}

public static void main(String[] args) {

    int[] arr0 = { 5, 2, 10, 4, 1, 11 };

    /* determine the size of the first array */
    float quotient = (float)arr0.length / 2;
    int mid = (int) Math.floor(quotient);

    int size = quotient != mid ? mid : mid - 1;

    /* Initialize arrays here */
    Integer[] arr1 = new Integer[size];
    Integer[] arr2 = new Integer[arr0.length - mid];

    List<Integer> list = intArrayTolist(arr0);

    /* Populate the first array with largest values
     * found within the main array
     */
    for (int i = 0; i < size; i++) {
        /*
         * Find out the largest value in the main array
         * and add that value to the first array
         */
        arr1[i] = java.util.Collections.max(list);
        list.remove(arr1[i]);
    }

    arr2 = list.toArray(arr2);
    int sum = Arrays.stream(arr0).sum();

    System.out.println("First array: " + Arrays.toString(arr1));
    System.out.println("Second array: " + Arrays.toString(arr2));
    System.out.println("Sum of all numbers: " + sum);
}

Output

First array: [11, 10]
Second array: [5, 2, 4, 1]
Sum of all numbers: 33

Note that it might not be as elegant I would have hopped but it gets the job done. I will see if I can do some further cleaning and optimizing as I feel there is a lot of redundancies in there. It's just a quick mock up so you can have something that actually works.