乘积最大和

Question

给定N个数字，范围为-100.100。

要求重新排列元素以使产品价值之和最大。此任务中的乘积和定义为a1*a2+a2*a3..an-1*an

例如，给定数字10 20 50 40 30。

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

预期的最大乘积为1342。

我的算法给出了下一个重排：

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()