產品的最大總和

Question

我遇到以下問題。

給定N個數字，範圍爲-100..100。

需要重新排列元素以使產品價值達到最大。在此任務產品 之和定義爲A1 * A2 + A2 * A3 ... AN-1 * AN

例如，給定數目10 20 50 40 30

然後，我們可以重新排列它們以下方式： 10,30,50,40,20從左邊開始最大爲10×30 + 30×50 + 50×40 + 40×20 = 4600

這個想法是對序列進行排序，然後將最大數字放在新序列的中間，然後將下一個最大數字放在右邊，然後再放到左邊，依此類推。 但是，關於負數，這是行不通的。

我曾嘗試下面的算法：

1）如何通過上述 4所描​​述的）從正序找到最小數目如何以上 3）處理負數描述排序的初始序列 2）過程的正數和零個值，它會是左邊或右邊的元素，並且在此數字處理負數序列之前添加。

例如，給定的序列：

1，-2,3，-4,5，-6,7，-8,9,10,11,12,13,14,15，-16

預期的產品的最高金額爲1342

我的算法給出下一重排：

3,7,10,12,14,15,13,​​11,9,5,1，-4 ，-8，-16，-6，-2

產品總和是1340.

這似乎工作，但它沒有。

您能否提供建議？

Answer 1

你的方法是合理的，但你必須分開正數和負數。

對數組進行排序並將其分成左右兩部分，一部分包含所有負數，另一部分包含所有非負數。按照之前的操作重新排列它們，中間的最大值（絕對值）和遞減值在兩側交替放置，但要確保每個部分中的最小值位於相反的兩端。

具體而言，絕對值最小的負數應該是左側部分的最後一個元素，而具有最小值的非負數應該是右側部分的第一個元素。

然後連接兩部分並計算相鄰產品的總和。

這裏有一個樣例：

arr = [2, 3, 5, -6, -2, -5] 
arr.sort() = [-6, -5, -2, 2, 3, 5] 
left, right = [-5, -6, -2], [2, 5, 3] 
max_sum_of_product = -5*-6 + -6*-2 + -2*2 + 2*5 + 5*3 = 63 

我沒有正確性的形式證明，但這種方法給出了相同的結果作爲蠻力搜索超過輸入數組的所有排列：

def max_sum_of_products(arr): 
    from itertools import permutations 
    n = len(arr) 

    ###### brute force method 
    max1 = max([sum([a[x-1]*a[x] for x in range(1,n)]) for a in permutations(arr)]) 

    ###### split method 
    lo, hi = [x for x in arr if x<0], [x for x in arr if x>=0] 
    lo.sort() 
    hi.sort() 
    lo_ordered, hi_ordered = [], [] 
    t = (len(lo)%2 == 1) 
    for x in lo: 
    if t: 
     lo_ordered = lo_ordered + [x] 
    else: 
     lo_ordered = [x] + lo_ordered 
    t = not t 
    t = (len(hi)%2 == 0) 
    for x in hi[::-1]: 
    if t: 
     hi_ordered = hi_ordered + [x] 
    else: 
     hi_ordered = [x] + hi_ordered 
    t = not t 
    arr = lo_ordered + hi_ordered 
    max2 = sum([arr[x-1]*arr[x] for x in range(1,n)]) 

    return (max1, max2) 

def test(): 
    from random import randint 
    for i in range(10): 
    a = [] 
    for j in range(randint(4,9)): 
     a = a + [randint(-10,10)] 
    print a, 
    (max1,max2) = max_sum_of_products(a) 
    if max2!=max1: 
     print "bad result :-(" 
    else: 
     print max1 

test() 

Answer 2

我在java中編寫了一個方法，它將數組作爲輸入並返回產品對的最大總和作爲輸出。

首先我計算負數部分，然後計算正數部分，然後返回它們的計算總和。 在計算負數部分時，如果元素的數量是奇數，則需要避免剩餘的元素（因爲它可以乘以0並且無效），所以我們這樣做是爲了使負數相加會降低總和。 所有其他負項都需要成對相乘和相加。

然後來到第二個正面部分，當我們看到1時，如果元素數是奇數，我們需要添加它，否則就簡單地乘以前進。

public static long sum(int arr[]) { 
    Arrays.sort(arr); 
    long ans = 0; 
    long ans1 = 0; 
    boolean flag = false; 
    boolean flag2 = false; 
    int[] arr1 = new int[arr.length]; 
    int[] arr2 = new int[arr.length]; 
    int i = 0; 
    while (arr[i] < 0) { 
     arr1[i] = arr[i]; 
     i++; 
    } 
    if (arr[i] == 0) flag = true; 

    if (i % 2 == 0) {        //even -6,-5,-3,-2,-1 
     for (int j = 0; j < i - 1; j += 2) { 
      ans = arr1[j] * arr1[j + 1]; 
     } 
    } else { 
     if (flag) { 
      for (int j = 0; j < i - 2; j += 2) { 
       ans = arr1[j] * arr1[j + 1]; 
      } 
     } 
    } 
    int j = 0; 
    while (i<arr.length) { 
     arr2[j] = arr[i]; 
     i++; 
     j++; 
    } 

    if (arr2[j] == 1) flag2 = true; 

    if (i % 2 == 0) { 
     for (int k=i-1; k>0; k-=2) { 
      ans1 = arr2[k] * arr2[k-1]; 
     } 
     if (flag2) ans1 = ans1 + 1; 
    } else { 
     for (int k=arr2.length-1; k>1; k-=2) { 
      ans1 = arr2[k] * arr2[k-1]; 
     } 
     ans1 = ans1 + arr2[0]; 
    } 
    return ans + ans1; 
}