查找给定阵列的元件的最大总和

Question

我必须找到数组中的元素之和最大（或它们的置换形式），元件的值的阵列

查找算法中取决于它们的位置在特定的阵列的合计如下

int taste = 0 
for (int i= 0; i <= N; i++){ 
    if (p[i]) - p[i-1]) >= 0): 
     taste += i * (p[i]) - p[i - 1]) 
    else: 
     taste += i * (p[i - 1] - p[i]) 

我的解决办法是蟒蛇，但我总是得到的结果为0

from itertools import permutations 
def sum_permuatations(): 
    t = int(input()) 
    taste = 0 
    maxTaste = 0 
    while (t!=0): 
     t = t-1 
     lent = input() 
     lis = input() 

     for p in permutations(lis, len(lent)): 
      for i in range(2,len(p)+1): 
       if (int(p[i]) - int(p[i-1]) >= 0): 
        taste += i*(int(p[i])-int(p[i-1])) 
       else: 
        taste += i*(int(p[i-1])- int(p[i])) 
      if taste > maxTaste: 
       maxTaste = taste 
     return maxTaste 

请帮我解决我的共同的错误德。

Answer 1

该解决方案还使用itertools库来生成各种排列。对于每个那些最大相邻和公式可以通过使用zip来计算列表中的连续数字对。函数enumerate也用于给出每对的位置。

import itertools 

input_list = [10, 15, 16] 
result = [] 

for perm in itertools.permutations(input_list): 
    sum_diff = 0 
    for i,pair in enumerate(itertools.izip(perm[:-1], perm[1:])): 
     sum_diff += abs(pair[0]-pair[1]) * (i+2) 
    result.append((sum_diff, perm)) 

result.sort() 
print result[-1] 

这将给予以下结果：

(28, (15, 10, 16)) 

或者，如果您打印整个列表：

[(13, (10, 15, 16)), (15, (10, 16, 15)), (17, (16, 15, 10)), (20, (15, 16, 10)), (27, (16, 10, 15)), (28, (15, 10, 16))] 

您的解决方案有几个小问题，使用range将启动0.对于每个置换，taste也需要归零，如下所示：

from itertools import permutations 

def sum_permuatations(lis): 
    maxTaste = 0 

    for p in permutations(lis): 
     taste = 0 
     for i in range(1,len(p)): 
      if (int(p[i]) - int(p[i-1]) >= 0): 
       taste += (i+1)*(int(p[i]) - int(p[i-1])) 
      else: 
       taste += (i+1)*(int(p[i-1]) - int(p[i])) 

     if taste > maxTaste: 
      maxTaste = taste 

    return maxTaste 

input_list = [10, 15, 16] 
print sum_permuatations(input_list) 

您将需要编辑它以提示输入，这只是使测试更容易。您可以编辑它以使用abs命令来避免需要按不同顺序进行减法。