Как найти «максимальную абсолютную сумму» функции с набором целых чисел

Question

Я пытаюсь решить эту проблему в C ++, изо всех сил пытаясь найти решение, которое является O (1).

Учитывая входной массив из четырех целых чисел, перемешайте их в таком порядке, чтоF(s) = abs(s[0]-s[1]) + abs(s[1]-s[2])+ abs(s[2]-s[3]) является максимальным (абсолютным).

Если целые числа являются уникальными, то существует максимум 24 возможных перемешиваний.

например,

A=5, B=3, C=-1, D=5

Перемешано в

A=5, B=-1, C=5, D=3

Результатом будет

F(s) = 14;

Этот алгоритм должен быть O (1).

Обратите внимание на сочетание отрицательных и положительных чисел.

F(s) = abs(s[0]-s[1]) + abs(s[1]-s[2])+ abs(s[2]-s[3])

Answer 1

Если вы сделаете все перестановки из 0, a, a+b, a+b+c (с a, b, c положительным), вы увидите, что максимум достигается для:

• a, a+b+c, 0, a+b
• и по симметрии a+b, 0, a+b+c, a

(в результате 2*a + 3*b + 2*c).

Нечитаемое решение ("сортировка" на месте):

int rearrange(int (&a)[4])
{
    if (a[3] < a[2]) {
        std::swap(a[3], a[2]);
    } // a[2] <= a[3]
    if (a[1] < a[0]) {
        std::swap(a[1], a[0]);
    } // a[2] <= a[3] && a[0] <= a[1]
    if (a[0] < a[2]) {
        std::swap(a[0], a[2]);
    } // a[2] <= a[3] && a[2] <= a[0] <= a[1] -> a[2] is the min
    if (a[1] < a[3]) {
        std::swap(a[1], a[3]);
    } // a[2] <= a[3] <= a[1] && a[2] <= a[0] <= a[1] -> a[1] is the max
    if (a[3] < a[0]) {
        std::swap(a[3], a[0]);
    } // a[2] <= a[0] <= a[3] <= a[1]
    // as we know order, we might get rid of abs:
    // (a[1] - a[0]) + (a[1] - a[2]) + (a[3] - a[2]);
    return -a[0] + 2 * a[1] - 2 * a[2] + a[3];
}

Демо