最大化总和

Question

给定N个不同的正整数列表的差异，分区列表成n/2大小的两个 子列表，使得所述子列表 的总和之间的差被最大化。 假设n是偶数并确定时间复杂度。

我知道，我知道这是一个家庭作业问题。但问题不一定在解决它，而是在了解究竟究竟在问什么。我可以肯定地说，问题的一半是简单解决，但我不觉得我得到的是什么

使得子列表 的总和之间的差异最大化的意思。

中说明的“进攻计划”任何帮助，将不胜感激

Answer 1

asuume你有这个列表

• list : 1 ,1 , 2, 3, 1, 5, 6, 1, 2, 20

这意味着你可以把它拆分在很多方面的大小为n/2的子列表 诸如此类

• sub list 1 : 3, 1, 5, 6, 1
• sub list 2 : 1 ,1 , 2, 2, 20

现在计算每个子列表

• sum of sub list 1 is 16
• sum of sub list 2 is 26
• diffrence between them is : 10

的总和10

但问题想两个子列表，例如有这个条件

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

这意味着我们可以分拆的主列表分为两个子列表选择具有问题条件单程所有方式。

例如，如果我们分裂上面所列内容到这个列表

• sub list 1 : 1 ,1 ,1 ,1 , 2

• sub list 2 : 2, 3, 5 , 6 , 20

• sum of sub list 1 is 6

• sum of sub list 2 is 36
• diffrence between them is : 30

哪个比上一个结果也是最大的