---

(1)思想：

为了使 |S₁ − S₂| 最大，我们需要将较大的数尽可能集中在一个子集，较小的数集中在另一个子集。具体来说：

• 如果 n 是偶数，我们需要选择 n/2 个最大的数和 n/2 个最小的数分别放在两个子集中。

• 如果 n 是奇数，我们需要选择 ⌈n/2⌉ 个最大的数和 ⌊n/2⌋ 个最小的数（或者反过来），这样和的差会更大。

步骤：

1. 将集合 A 排序。

2. 将较大的 ⌈n/2⌉ 个数放入一个子集，剩下的 ⌊n/2⌋ 个数放入另一个子集。

   • 这样 |n₁ − n₂| ≤ 1，满足最小。

   • 同时，较大的数集中在一个子集，较小的数在另一个子集，使得 |S₁ − S₂| 最大。

（3）

int Partition(int a[], int low, int high) { 
	int pivot = a[low];
	while (low < high) {
		while (low<high && a[high]>=pivot) high--;
		a[low] = a[high];
		while (low < high && a[low] <= pivot) low++;
		a[high] = a[low];
	}
	a[low] = pivot;
	return low;
}
void QuickSort(int a[], int low,int high) {
	if (low < high) {
		int pivotLoc = Partition(a, low, high);
		QuickSort(a, low, pivotLoc-1);
		QuickSort(a,pivotLoc+1, high);
	}
}
int partitionA(int a[], int n) {
	QuickSort(a, 0, n - 1); /...