W我有一个数组0..N-1
我需要将它们分成两组：说K和N-K元素。
但条件是：sum(N-K)-sum(K)应该是最大值。
我该如何处理？
我试过这样做：对数组进行排序 - std::sort(W,W+N)，然后：
for(int i=0; i<K; ++i) less+=W[i];
for(int i=K; i<N; ++i) more+=W[i];
进而more-less
但我认为这不是最佳方式，或者在某些情况下甚至可能是错误的。
谢谢。
更新：
我们必须从中选择K元素，W使得sum(k elements) 和之间的差异sum(remaining elements)最大。
编辑：请注意，在您发布的问题中，您似乎期望排序从高到低排序。两者都std::sort将std::nth_element低元素放在首位。我已在下面的答案中替换K为(N-K)更正此问题。
更新后编辑：执行以下两次，一次 forK和一次 for (N-K)。选择最佳答案。
std::sort比std::nth_element您的目的更优化。
std::nth_element( W, W+(N-K), W+N );
您的使用std::sort将使用 O(n log n) 复杂性来对您不需要的两个集合中的所有元素进行排序。
std::nth_element将使用 O(n) 复杂度进行分区而不完全排序。
注意：您的 for 循环也可以替换为std::accumulate
less = std::accumulate( W, W+(N-K), 0 );
more = std::accumulate( W+(N-K), W+N, 0 );
您要将元素集拆分为两个不同的不重叠子集 A 和 B。您希望 sum(A)-sum(B) 尽可能高。
因此，您希望 sum(A) 尽可能高，而 sum(B) 尽可能低。
因此，集合“A”应包含尽可能高的元素，
而集合“B”应包含尽可能低的元素
通过按元素的值对输入集进行排序，并将“最低元素”分配给 B，将“最高元素”分配给 A，可以保证 sum(A)-sum(B) 将是最大可能的。
我没有看到您的方法是错误的任何情况。
至于“最优”的东西，我根本没有分析。德鲁的笔记似乎很有可能。
可以使用max heap. O(n + n log k)时间
制作一个 size 的最大堆k。我们找到k了数组的最低元素。堆的元素将root是堆中的最高元素。Make a heap of first k elements.
现在遍历数组。将数组元素与root最大堆的元素进行比较。如果它小于 root 则替换它并再次堆化堆。这将花费 O(n log k) 时间。求堆元素的总和。
现在您可以找到数组其余元素的总和并获得差异。( O(n)) 时间
总时间O(n + n log k)
编辑：也许您可以在遍历堆时找到数组所有元素的总和。这将节省O(n)时间，并且可以解决O(n log k)