Amazon 面试题， Four Integers 问题解法

大家好， 又有问题需要求助了！

最近刷题遇到了four integers 问题， 就是给 4 个整形数， 通过交换他们的位置，使F(S)= abs(S[0]-S[1]) + abs(S[1]-S[2]) + abs(S[2]-S[3]） 的值最大。

大家有什么思路吗？ 万分感谢！

这题可以重新表述一下：数轴上有a，b，c，d四个点（不妨设a < b < c < d），从某个点出发，沿数轴访问其它点各一次，问路径的最大长度是多少。

比如说
(1) 路径

1. a --> b --> c --> d

复制代码

的长度为|ab| + |bc| + |cd|

(2) 路径

1. a --------> c
   
2.       b <--
   
3.         --------> d

复制代码

的长度为|ab| + 3|bc| + |cd|


可能的组合并不多，稍微枚举一下可以发现最长的是这条：

1. a <-------- c
   
2.   --------------> d
   
3.       b <--------

复制代码

长度为2|ab| + 3|bc| + 2|cd| -- 按照c，a，d，b的顺序。

而由a，b，c，d变换到c，a，d，b，一种可行方法就是

第一个数和第二个数交换， 第三个数和第四个数交换， 再第一个数和第四个数交换

PS: 如果要严格证明的话，可以用枚举+排除的方法，因为路径总数只有4!=24种，其中还有一部分是由对称性而重复的。

我觉得可以这样想，假设a1<a2<a3<a4, 那么a4-a1, a4-a2是最大的两个差，所以一定要a1, a4, a2 或者 a2, a4, a1. 至于a3 放哪，看一看发现a2, a4, a1, a3是最大的。 当然， a3, a1, a4, a2也是一样的

grady0407 发表于 2016-9-20 22:38
我觉得可以这样想，假设a1

嗯我看网上有网友的答案是。 把这个四个int值给排序，然后将 第一个数和第二个数交换， 第三个数和第四个数交换， 再第一个数和第四个数交换。。。这是啥

我也想知道为什么,求好心人解答

面试的时候出不了最优解直接暴力解再排除也行的，情况也没多少。这种需要纸和笔的电面要怎么说？
最大和最小的肯定在最中间，2种排列方式，后面再对中间两种试个两次也很简单。

请问这个问题是面巾里的吗？ 刷题的tag里没有这个诶。。难道我刷的是假题...

可以用全排列吗？ 总共也就 （4！）种情况啊