第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{/beginpublic 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();}
}