408 true question - division sequence

• Problem description

Known by n A set of positive integers A, Divide it into two subsets that do not want to intersect A1 and A2, The number of elements is n1 and n2,A1 and A2 The sum of the elements in is S1 and S2, Design an algorithm as efficient as possible , Satisfy |n1-n2| Minimum and |S1-S2| Maximum .

•   Algorithmic thought

n2-n1 The minimum is that the two subsequences are half each , And all the elements in half are smaller than any element in the other half

Here you can take advantage of the idea of quick sorting , When the final position of the current pivot is n/2 when , Then stop sorting , Sum and difference the elements of the left and right sequences

• Algorithm implementation

void partition(int a[],int low,int high,int n){
	int pivot=a[low];
	int temp_low=low;
	int temp_high=high;
	while(low<high){
		while(low<high&&pivot<=a[high])--high;
		a[low]=a[high];
		while(low<high&&pivot>a[low])++low;
		a[high]=a[low];
	}
	a[low]=pivot;
	
	if(low==n/2)// find n/2 Element number  
	return;
	partition(a,temp_low,low-1,n);
	partition(a,low+1,temp_high,n);
	
}

• The test case

#include<stdio.h> 
void partition(int a[],int low,int high,int n){
	int pivot=a[low];
	int temp_low=low;
	int temp_high=high;
	while(low<high){
		while(low<high&&pivot<=a[high])--high;
		a[low]=a[high];
		while(low<high&&pivot>a[low])++low;
		a[high]=a[low];
	}
	a[low]=pivot;
	
	if(low==n/2)// find n/2 Element number  
	return;
	partition(a,temp_low,low-1,n);
	partition(a,low+1,temp_high,n);
	
}
int main(){
	int a[]={10,2,5,6,88,23,25,9};
	partition(a,0,7,8);
	int i,s1=0,s2=0;
	for(i=0;i<4;i++)
		s1+=a[i];
	for(;i<8;i++)
		s2+=a[i];
		printf("%d\n",s2-s1);
		printf("%d\n",s2);
}

• Running results