408真题——划分序列问题描述 算法思想算法实现测试用例运行结果
问题描述 已知由n个正整数构成的集合A，将其划分为两个不想交的子集A1和A2，元素个数分别是n1和n2，A1和A2中的元素之和分别为S1和S2，设计一个尽可能高效的算法，满足|n1-n2|最小且|S1-S2|最大。 算法思想 n2-n1最小即为两子序列各为一半，且一半的所有元素比另外一半的任意元素都要小此处可利用快速排序的思想，当当前的枢轴的最终位置是n/2时，则停止排序，对左右序列的元素进行求和做差即可 算法实现 void partition(int a[],int...
