产品的最大总和

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) 排序初始序列 2) 如上所述处理正数和零值 3）如何处理负数如上所述 4) 从正序中找到最小数，它可以是左元素或右元素，并在这个数处理负序之前添加之后。

例如给定序列：

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中写了一个方法，它将数组作为输入，return产品对的最大总和作为输出。

首先我计算负数部分，然后是正数部分，然后 return 它们的计算总和。在计算负数部分时，如果元素个数为奇数，则需要避免剩余元素（因为它可以乘以 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;
}

产品的最大总和

Maximum Sum of Product

algorithm

sequence

maximize