最大化相邻数字的乘积之和

Question

这是我在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

Answer 1

当最大值在序列的中间时,最大相邻和的乘积出现,并且连续的较低值在其左右交替出现.也就是说,给定值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