algorithm - 和差最大化

Question

Given a list of N distinct positive integers, partition the list into two sublists of n/2 size such that the difference between sums of the sublists is maximized. Assume that n is even and determine the time complexity.

我知道我知道，这是一道作业题。但问题不一定在于解决它，而是在于理解到底在问什么。我可以肯定地说，一半的问题很容易解决，但我不认为我明白

such that the difference between sums of the sublists is maximized.

如果能帮助说明“攻击计划”，我们将不胜感激

Answer 1

假设你有这个列表

• 列表:1 ,1 , 2, 3, 1, 5, 6, 1, 2, 20

这意味着您可以通过多种方式将其拆分为大小为 n/2 的子列表像这样

• 子列表 1 : 3, 1, 5, 6, 1
• 子列表 2 : 1 ,1 , 2, 2, 20

现在计算每个子列表的总和

• 子列表 1 的总和为 16
• 子列表 2 的总和为 26
• 它们之间的差异是:10

但是问题想要两个子列表这样有这个条件

• 问题条件:子列表之和之间的差异最大化。

这意味着在我们可以将主列表拆分为两个子列表的所有方式之间选择一种具有问题条件的方式。

例如，如果我们将上面的列表拆分成这个列表

• 子列表 1 : 1 ,1 ,1 ,1 , 2

• 子列表 2 : 2, 3, 5 , 6 , 20

• 子列表 1 的总和为 6

• 子列表 2 的总和为 36
• 它们之间的差异是:30

大于上一个结果也是最大值