java - 数组子集不等和

Question

我需要编写一个函数来将数组分成两部分 {4,5,2,1,3}，这样第一个数组中的总和大于第二个数组中的总和，但第一个数组的长度小于第二个。他们的总和的并集是总和，他们没有任何交集。所以，答案是{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());




        }
    }

它不会返回预期的答案。它并没有像我编写的代码那样从堆栈中弹出。有人可以帮助我做错什么吗。

Answer 1

据我所知，没有任何问题，一切都按预期进行。唯一的问题是弹出操作以相反的顺序给你结果。我已经在下面的代码中修复了这个问题:

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));

输出 [4, 5]

编辑:这里是您问题的完整解决方案:

/**
 * 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);
}

输出

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

请注意，它可能不像我希望的那样优雅，但它完成了工作。我会看看是否可以做一些进一步的清理和优化，因为我觉得那里有很多冗余。这只是一个快速的模型，因此您可以获得实际可行的东西。