2

这是我在Interviewstreet 代码打印期间遇到的一个问题。我无法找到解决方案，甚至无法思考其方向。如果有人可以帮助我找到灵魂，或者向我解释需要如何处理问题，我将不胜感激。

给定数字 1, 2, 3, .., N，按顺序排列它们，使相邻数字的乘积之和最大化。

例如：如果 N = 3，我们将它们排序为 (1, 2, 3)，则产品的总和为 1*2 + 2*3 = 8，如果我们将它们排序为 (1, 3,2)，则总和产品数量为 1*3 + 3*2 = 9。

输入格式：

输入的第一行包含 T，即测试用例的数量。然后按照 T 行，每行包含一个整数 N。

输出格式 ：

对于每个测试用例，打印相邻数字乘积的最大总和。

样本输入：

2 2 4

样本输出：

2 23

解释 ：

在第一个测试用例中，给定的排列是 (1, 2)。所以乘积的最大总和是 1*2。在第二个测试用例中，数字是 (1,2,3,4)。排列 1,3,4,2 的相邻数字的乘积之和为 1*3+3*4+4*2 = 23。没有其他排列的相邻数字的乘积之和超过 23。

约束：

1 <= T <= 10 1 <= N <= 200000

4

2 回答 2

6

当最大值位于序列的中间时，最大的相邻乘积和出现，并且连续较低的值在其左右交替。也就是说，给定值 n 的序列将是 [..., n-3, n-1, n, n-2, n-4, ...] （或与此相反，它将具有相同的产品总和）。

因此，省略输入解析位，这是算法的核心（在 Python 中，但很容易翻译成其他语言）：

def maximumSumOfAdjacentProducts(n):
    if n == 1: # special case needed for a one element sequence
        return 1

    sumOfProducts = n * (n-1) # this pair is the "center" of the sequence

    for i in range(n-2, 0, -1): # iterate downward from n-2 to 1
        sumOfProducts += i*(i+2) # each adjacent pair is separated by 2

    return sumOfProducts
于 2012-06-17T01:56:25.813 回答
1

  1. 对数组进行排序，sortedArray按升序调用。

  2. 删除max1，max2并将它们放在一个result列表中。

  3. 删除下一个元素并将其添加到MAX(max1, max2).

  4. 更新max1和max2. 即在列表max1的左侧和max2右侧。

  5. 重复步骤 3 和 4，直到排序后的输入数组包含元素。

例子： 

inputArray: 1,3,4,2,5

sortedArray: 1,2,3,4,5

Add 5 and 4 to the list first.

result = [5, 4]

Remove 3 and add it to MAX(5,4)

result = [3, 5, 4]

Remove 2 and add it to MAX(3,4)

result = [3, 5, 4, 2]

Remove 1 and add it to MAX(3,2)

result = [1, 3, 5, 4, 2]
于 2012-06-17T01:51:59.957 回答