Four Integers

Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.

解法：

void foobar(vector<int> vec)
{
    assert (vec.size() == 4);

    sort(vec.begin(), vec.end());
    // 2 4 1 3 or 3 1 4 2
    vector<int> tmp(4);
    tmp[0] = vec[1];
    tmp[1] = vec[3];
    tmp[2] = vec[0];
    tmp[3] = vec[2];
    cout << "order: ";
    for (int i = 0; i < tmp.size(); ++i)
        cout << tmp[i] << ", "; // don't care about the last comma
    cout << endl;
    cout << "result: " << fabs(tmp[0] - tmp[1]) + fabs(tmp[1] - tmp[2]) + fabs(tmp[2] - tmp[3]) << endl;
}

这个本质上来说是一个数学解法，当排序后的数组，2412和3142两种方式排列能使公式值最大。

证明：
假设排序后的数组为 a[0], a[1], a[2], a[3]，令
x = abs(a[1] - a[0])
y = abs(a[2] - a[1])
z = abs(a[3] - a[2])
题目上本质是上两两求差值，求三个差值最大时的四个数的排列情况。
当四个数不需要全部被使用时，F(S) 最大为 3 * (a[3] - a[0])，即3 * (x + y + z)，基于题设，现在需要将公式 3 * (x[3] - a[0]) 中的一个a[0]，一个 a[3] 替换成 a[1]，a[2]。替换后最理想的情况是，a[3] 换成 a[2]，a[0]换成 a[1]，使 F(S)最大，为2x + 3y + 2z。其他情况都小于此值，与 x y z 值大小无关。