arrays - 找到数组中两个子数组之和的最小绝对差

Question

我有一个包含 N 个元素的数组(未排序)。数组的每个元素可以是任何整数(正数或负数)。现在我必须以 absolute(sum(sub_array1) - sum(sub_array2)) 最小的方式对该数组进行分区。

例子: A = {3, 4, 1, 2, -5}

partition1 = sub_array1 {3}, sub_array2 {4, 1, 2, -5} => abs(3-2) = 1

partition2 = sub_array1 {3, 4}, sub_array2 {1, 2, -5} => abs(7-(-2)) = 9

partition3 = sub_array1 {3, 4, 1}, sub_array2 {2, -5} => abs(8-(-3)) = 11

partition4 = sub_array1 {3, 4, 1, 2}, sub_array2{-5} => abs(10-(-5)) = 15

答案 = 1

我已经用 O(N^2) 实现了解决方案，但我想至少用 O(Nlog(N)) 实现它，并且没有线程(并行解决方案)。

Answer 1

这可以在线性时间内完成，通过观察两个分区的总和是常数:

• 对数组中的所有元素求和(称之为S)。
• 遍历数组，计算部分和(在步骤 i 中调用此 P_i)。
• 在迭代时，找到 i 使得 abs(P_i - (S - P_i)) 最小化。