Non-Leetcode Questions: Four Integers
有4个正数，A,B,C,D。改变他们的位置使得他们两两之间的距离之和最大。Naive Way ：先写一个例子，1 3 4 6。如果采用一种greedy 的方法，第一个固定，第二个挑距离最大的6，第三个挑4，最后是3。这样下来 5 + 3 + 1 = 8。很明显，3和4放在一起距离太小了，把他们分开放最好。于是有了3 1 6 4，这样还是不如 4 1 6 3大。因为最大的和最小的会创造最大距离，而且他们离中间的两个都可以再差一个数，这样将一头一尾放在中间，然后中间两个分立两边，可造成最大距离和。
Read full article from Non-Leetcode Questions: Four Integers
No comments:
Post a Comment