第1关：求解一个整数数组划分为两个子数组问题

[TOC]求解一个整数数组划分为两个子数组问题

任务描述
已知由n(n>=2)个整数正整数构成的集合A={ak}(0<=k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中的元素之和分别为S1和S2.设计一个尽可能高效的划分算法,满足|n1-n2|最小且|S1-S2|最大,算法返回|S1-S2|的结果.

本关任务：编写一个能返回|S1-S2|的结果的小程序。

解法提示
将A中最小的「n/2」个元素放在A1中,其他 元素放在A2中,即得到题目要求的结果.采用递归快速排序思路,查找第n/2小的元素,前半部分为A1的元素,后半部分为A2的元素,这样,算法的时间复杂度为O(n).如果将A中元素全部排序,再进行划分,时间复杂度为O(nlog2n),不如前面的方法.
输入描述:输入的第1行包含一个整数n,表示给定数字的个数;第2行包含n个整数,相邻的整数之间用一个空格分隔,表示给定的整数.

输出描述
输出三行,第1行输出求解结果,即|S1-S2|的值
第2、3行输出划分结果：
第2行输出A1：中的元素，空格隔开
第3行输出A2：中的元素，空格隔开

输入描述
输入一个整数n，表示元素的个数
再输入n个整数

编程要求
根据提示，在右侧编辑器补充代码，计算并输出|S1-S2|的结果。

测试说明
平台会对你编写的代码进行测试：

测试输入：9
4,3,5,7,9,2，1，6，8；
预期输出：
求解结果：25
划分结果：A1：2 3 1 4
A2：9 7 5 6 8

测试输入：5
15，13，12，100，20；
预期输出：
求解结果：110
划分结果：A1：12 13
A2：15 100 20

开始你的任务吧，祝你成功！

package step1;
import java.util.Arrays;
import java.util.Scanner;
 public class  Int_array_split_empty{
       /begin

 public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        
        int n = scanner.nextInt();
        
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int result = solve(a, n);
        System.out.println("求解结果：" + result);
        
        System.out.print("划分结果：A1：");
        display(a, 0, n / 2 - 1);
        System.out.print("A2：");
        display(a, n / 2, n - 1);
        
        scanner.close();
    }

    public static int partition(int[] a, int low, int high) {
        int i = low, j = high;
        int pivot = a[low];
        while (i < j) {
            while (i < j && a[j] >= pivot) {
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i] <= pivot) {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = pivot;
        return i;
    }

    public static int solve(int[] a, int n) {
        int low = 0, high = n - 1;
        int flag = 1;
        while (flag != 0) {
            int i = partition(a, low, high);
            if (i == n / 2 - 1) {
                flag = 0;
            } else if (i < n / 2 - 1) {
                low = i + 1;
            } else {
                high = i - 1;
            }
        }
        
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n / 2; i++) {
            s1 += a[i];
        }
        for (int j = n / 2; j < n; j++) {
            s2 += a[j];
        }
        return s2 - s1;
    }

    public static void display(int[] a, int low, int high) {
        for (int i = low; i <= high; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}