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が含まれています。次に、それぞれが整数Nを含むT行に従います。

出力フォーマット ：

テストケースごとに、隣接する数値の積の最大合計を印刷します。

サンプル入力：

2 2 4

サンプル出力：

2 23

説明 ：

最初のテストケースでは、順列は（1、2）です。したがって、積の最大合計は1*2です。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 に答える