两个连续数的最大和

Question

假设我们有N个数，我们必须以这样的方式排列这些数，使我们得到两个连续数之和为最大值。

例如: 18,20,16,12

这里两个连续的数字之和是(18+20)+(20+16)+(16+12)= 38+36+28=102，但是我们可以这样排列上面的数字

12、20、18、16

哪里

(12+20)+(20+18)+(18+16)= 32+38+34=104

有人能帮我做这个吗。我需要为此编写一个java程序。

Answer 1

如果您有N个数字，则要使连续数的和最大化。

{a，b，c，d，e} ->(a+b)+(b+c)+.(d+e)

代数化简

(a+ 2b + 2c +.+ 2d +e)

若要使此最大化，只需将最低值编号作为a或e。

因此，如果对列表进行排序，然后取最小的2个元素，并将一个元素放在末尾，另一个元素放在前面，那么内部顺序就无关紧要了。