序列重排-求相邻差和最大（京东笔试题）

本文主要是介绍序列重排-求相邻差和最大（京东笔试题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：序列重排-求相邻差和最大

分析:数学题，分析 找规律

来源：京东笔试题（2021-9-12）

'''
题目：序列重排
    给一个长度为n的序列A，你可以将序列中的元素按任意顺序重新排列，请你找到一种排列方式使得相邻两个数的差值之和最大，输出该最大值。
    即若重拍后的序列是B，你需要使 |B1-B2|+|B2-B3|+···+|Bn-1-Bn|的值最大

    例： 输入       输出 8
            3
            5 1 5
        输入          输出 8
            5
            5 2 2 2 1
分析：
    先按照升序排序！！！
    例  1 2 3 4 5          1 2 3 5
        3   5    4          3        5
          1    2                 1       2
    排序后的序列B 一定 满足 高低高低的这种排列方式如上例所示
    对于 1 2 5             从左边分析可以看到，             可以重写为：
        5 - 1   5 - 2        1 2 被减了两遍               -1 -1 - 2 - 2
        3 - 1                5 被加了两遍                 +5 +5
        4 - 2                3 4 在两边 各被加了一遍        +4 +4 +3 +3 -4 -3
    对于 1 2 3 5           分析可知
        5 - 1   5 - 2        1 被减了两遍                 -1 -1
        3 - 1                5 被加了两遍                 +5 +5
                             2 3 在两边分别被减了、加了一遍  -2 -2 +3 +3 +2 -3
    综上所述，可以将数组进行排序,
        如果数组元素为奇数个：前边n/2个元素（low），后边n/2+1个元素（high）
            (sum(high)-sum(low))*2 - high[0]-high[1]  (当个数是奇数时，让high中比较小的值在两边)
        如果数组元素为偶数个：前边n/2个元素（low），后边n/2个元素（high）
            (sum(high-sum(low)))*2 - high[0] + low[-1] (当个数是偶数时，让high中比较小的值在第一个，low中比较大的值在最后一个)

'''


def getMax(nums):
    nums.sort()
    mid = len(nums) // 2
    low, high = nums[:mid], nums[mid:]
    if len(nums) % 2 != 0:
        return (sum(high) - sum(low)) * 2 - high[0] - high[1]
    else:
        return (sum(high) - sum(low)) * 2 - high[0] + low[-1]


nums = list(map(int, input().strip().split()))
print(getMax(nums))

路虽远，行则将至。事虽难，做则必成 

这篇关于序列重排-求相邻差和最大（京东笔试题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！