Определение максимального значения выражения (анти-сортировка)

#cpp #алгоритм

Дано число n. Далее задана последовательность n чисел. Определить 
максимальное значение этого выражения: 


  |M1 - M2| + |M2 - M3| + ... + |Mn-1 - Mn|.


Пример:  


  Ввод:  5 1 3 5 7 9
  
  Вывод: 22  
  
  Максимальное значение 22, так как:  
  
  |3 - 9| + |9 - 1| + |1 - 7| + |7 - 5| = 22


Мой пример решения  (иногда выдает не правильный ответ) 

Идея решения : Сначала я упорядочил массив методом пузырька.
Всего пар  ( |M1 - M2| , |M2 - M3|, ... , |Mn-1 + Mn| ) будет n-1. Если в выражении
раскрыть модуль, то: 

Если a >= b : |a - b| = a - b
Если a < b : |a - b| = b - a.

То есть возле каждого числа стоит + или -. Их равное количество и равняется n-1.
Каждое число используется в выражении дважды (кроме первого и последнего (M1, Mn)
). Чтобы сумма вышла максимальной возле больших чисел ставил +, возле меньших -.

#include 
#include 
using namespace std;

int main()
{
  int n,plus,minus;
  cin>>n;
  double s = n;
  plus = n-1;
  minus=n-1;
  int sum = 0;
  int arr[n];
  for(int i = 0; i < n; i++)
      {
          cin>>arr[i];
      }
  for(int i = 0; i < n-1; i++)
      {
          for(int j = 0; j < n-i-1; j++)
              {
                  if(arr[j]>arr[j+1])
                  swap(arr[j],arr[j+1]);
              }
      }

      for(int i = 0; i < n-round((s-1)/2+0.1); i++)
          {
              sum-=arr[i];
              minus--;
          }


      for(int i = 0; i < n; i++)
          {
              if(minus>0)
              {
                  sum-=arr[i];
                  minus--;
              }

              if(minus>0)
              {
                  sum-=arr[i];
                  minus--;
              }
          }
          for(int i = n-1; i >=0; i--)
          {
              if(plus>0)
              {
                  sum +=arr[i];
                  plus--;
              }

              if(plus>0)
              {
                  sum +=arr[i];
                  plus--;
              }
          }

          cout<

Ответы
Ответ 1

"Жадный" алгоритм, уверенности в оптимальности которого пока нет:


Сортируем значения по возрастанию
 
    M1, M2, ..., Mn
Обходим ("прыгаем") значения в порядке туда-сюда снаружи-к-центру:
 
    M1, Mn, M2, Mn-1, M3, Mn-2...
 
пока не придем в последнюю вершину M[n/2]
Из нее "прыгаем" в M1, тем самым замыкая цикл
Из полученного цикла обхода вершин удаляем самое короткое ребро, т.е. ребро (i, j)
с минимальным значением |Mi-Mj|. Это будет либо последний прыжок с шага 2, либо прыжок
с шага 3
Оставшаяся цепь дает максимальную сумму (предположительно) 




Однако алгоритм пока не верен. Если следовать той же самой интуиции, то нам надо
попробовать те же самые "прыжки", но начиная с последнего элемента массива. Например,
на входе { 2, 4, 5, 7, 9 } вышеприведенный алгоритм даст 

|5 - 2| + |2 - 9| + |9 - 4| + |4 - 7| = 18


в то время как начиная "прыжки" с последнего элемента мы можем получить

|5 - 9| + |9 - 2| + |2 - 7| + |7 - 4| = 19


Другими словами, рассмотреть вышеприведенным алгоритмом следует как отсортированный
по возрастанию набор чисел, так и отсортированный по убыванию. Есть подозрение, что
рассмотрев оба варианта и выбрав лучший из двух, мы все таки найдем максимум. 

(Интуиция и эксперимент подсказывают, что такое явление может наблюдаться только
на наборах с нечетным количеством элементов. Это, по-идее, должно быть несложно доказать.
Также, в случае нечетного количества элементов скорее всего есть критерий, позволяющий
заранее увидеть, какой из двух вариантов лучше, не прогоняя всего алгоритма. Но пока,
на всякий случай, будем честно проверять оба варианта всегда.)

Интенсивное тестирование в сравнении с переборным алгоритмом пока не выявило нарушений.



#include 
#include 
#include 
#include 

int max_sum(const int a[], int n)
{
  int w_sum = 0;

  int 
    j_last = n / 2, 
    i_last = j_last + (n % 2 == 0 ? -1 : +1);
  int
    w_last = std::abs(a[j_last] - a[i_last]), 
    w_closing = std::abs(a[j_last] - a[0]);

  bool plus = false;

  if (w_closing > w_last)
  {
    std::cout << "|" << a[j_last] << " - " << a[0] << "|";
    w_sum += w_closing; 
    plus = true;
  }

  for (int i = 0, step = n - 1, j = i + step; j != j_last; 
         i = j, step = -step - (step < 0) + (step > 0), j = i + step)
  {
    std::cout << (plus ? " + " : "") << "|" << a[i] << " - " << a[j] << "|";
    w_sum += std::abs(a[j] - a[i]); 
    plus = true;
  }

  if (w_closing <= w_last)
  {
    std::cout << (plus ? " + " : "") << "|" << a[i_last] << " - " << a[j_last] << "|";
    w_sum += w_last; 
  }

  std::cout << " = " << w_sum << std::endl;

  return w_sum;
}

int main()
{
  int a[] = { 2, 4, 5, 7, 9 };
  int n = std::size(a);

  std::sort(a, a + n);
  int sum1 = max_sum(a, n);

  std::reverse(a, a + n);
  int sum2 = max_sum(a, n);

  std::cout << "Best = " << std::max(sum1, sum2) << std::endl;
}


Ответ 2

ЧАСТНЫЕ СЛУЧАИ

В частных случаях решение можно получить перебором всех возможных комбинаций.



Программа (C#):

    public static int[] FactGen(int n)
    {
        int[] fact = new int[n + 1];

        fact[0] = 1;
        for (int i = 1; i < n + 1; i++)
            fact[i] = i * fact[i - 1];

        return fact;
    }

    public static int[] PermsGenerator(int[] arr, int num, int[] fact)
    {
        int i, j, f, newind, newnum, newval, size = arr.Length;
        int[] result = new int[size];

        Array.Copy(arr, result, size);
        for (i = 0, newnum = num; i < size - 1; i++)
        {
            newind = newnum / (f = fact[size - 1 - i]);
            newnum = newnum - newind * f;
            newval = result[i + newind];
            for (j = i + newind; j > i; j--)
                result[j] = result[j - 1];
            result[i] = newval;
        }

        return result;
    }

    public static int SumAbs(int[] arr)
    {
        int sum = 0, prev = arr[0];

        foreach (int value in arr)
        {
            sum += Math.Abs(value - prev);
            prev = value;
        }

        return sum;
    }

    public static int[] MaxArr(int[] arr, bool detprn)
    {
        int i, j, sum, smax = -1, size = arr.Length;
        int[] perm, result = new int[size], fact = FactGen(size),
            sorted = new int[size], empire = new int[size];

        Array.Copy(arr, sorted, size);
        Array.Sort(sorted);
        for (i = 0; i < fact[size]; i++)
        {
            if ((sum = SumAbs(perm = PermsGenerator(sorted, i, fact))) > smax) {
                smax = sum;
                result = perm;
            }
            if (detprn)
            {
                Console.Write("\nПерестановка:  ");
                foreach (int value in perm)
                    Console.Write(value + "  ");
                Console.Write("    Сумма:  {0}   Максимальная сумма: {1}", sum, smax);
            }
        }
        Console.Write("\nИсходная выборка:  ");
        foreach (int value in arr)
            Console.Write(value + "  ");
        Console.Write("\nОтсортированная выборка:  ");
        foreach (int value in sorted)
            Console.Write(value + "  ");
        Console.Write("\nЛучшая перестановка:  ");
        foreach (int value in result)
            Console.Write(value + "  ");
        Console.WriteLine("\nМаксимальная сумма:  {0}", smax);
        empire[0] = sorted[i = size / 2 - 1];
        empire[1] = sorted[i + 2];
        empire[size - 1] = sorted[i + 1];
        for (i = 2, j = 0; i < size - 1; i++, j = (size) - 1 + ((i + 1) & 1) - j)
            empire[i] = sorted[j];
        Console.Write("Эвристический алгоритм:  ");
        foreach (int value in empire)
            Console.Write(value + "  ");
        Console.WriteLine("\nСумма:  {0}", SumAbs(empire));
        return result;
    }

    static void Main(string[] args)
    {
        bool binc;
        int i, j, n, nmax = 10;
        int[] arr;
        Random rand = new Random();

        MaxArr(new int[] { 1, 2, 3, 4 }, false);
        MaxArr(new int[] { 1, 2, 3, 4, 5 }, false);
        for (n = 6; n < nmax + 1; n++)
        {
            arr = new int[n];
            for (i = 0; i < n;)
            {
                arr[i] = rand.Next(1, 5 * n);
                binc = true;
                for (j = 0; j < i; j++)
                    binc &= (arr[i] != arr[j]);
                if (binc)
                    i++;
            }
            MaxArr(arr, false);
        }
    }




Результаты:


Исходная выборка:  1  2  3  4
Отсортированная выборка:  1  2  3  4
Лучшая перестановка:  2  4  1  3
Максимальная сумма:  7
Эвристический алгоритм:  2  4  1  3
Сумма:  7

Исходная выборка:  1  2  3  4  5
Отсортированная выборка:  1  2  3  4  5
Лучшая перестановка:  2  4  1  5  3
Максимальная сумма:  11
Эвристический алгоритм:  2  4  1  5  3
Сумма:  11

Исходная выборка:  26  10  21  4  27  5
Отсортированная выборка:  4  5  10  21  26  27
Лучшая перестановка:  10  26  4  27  5  21
Максимальная сумма:  99
Эвристический алгоритм:  10  26  4  27  5  21
Сумма:  99

Исходная выборка:  34  3  32  16  28  27  26
Отсортированная выборка:  3  16  26  27  28  32  34
Лучшая перестановка:  26  28  3  32  16  34  27
Максимальная сумма:  97
Эвристический алгоритм:  26  28  3  34  16  32  27
Сумма:  97

Исходная выборка:  27  3  34  38  18  29  31  39
Отсортированная выборка:  3  18  27  29  31  34  38  39
Лучшая перестановка:  29  34  3  38  18  39  27  31
Максимальная сумма:  128
Эвристический алгоритм:  29  34  3  39  18  38  27  31
Сумма:  128

Исходная выборка:  40  27  4  9  32  35  41  39  2
Отсортированная выборка:  2  4  9  27  32  35  39  40  41
Лучшая перестановка:  32  2  39  4  40  9  41  27  35
Максимальная сумма:  223
Эвристический алгоритм:  27  35  2  41  4  40  9  39  32
Сумма:  221

Исходная выборка:  41  35  45  27  34  33  18  24  16  25
Отсортированная выборка:  16  18  24  25  27  33  34  35  41  45
Лучшая перестановка:  27  34  16  35  18  41  24  45  25  33
Максимальная сумма:  150
Эвристический алгоритм:  27  34  16  45  18  41  24  35  25  33
Сумма:  150


Таким образом:


Нашлась более удачная комбинация для исходного массива.
Контрпример для эвристического алгоритма нашёлся не сразу.




ОБЩЕЕ РЕШЕНИЕ (10.02.2018)

Пусть
a = {a0 = M1, a1 = M2, …, an-2 = Mn-1, an-1 = Mn} -
 исходная последовательность,
b = {b0, b1, …, bn-2, bn-1} -та же последовательность в порядке возрастания,
с = {c0, c1, …, cn-2, cn-1} -требуемая последовательность.

Рассмотрим по отдельности случаи чётного и нечётного n.



Случай n = 2k

S(a) = Sц(a)  - |an-1 - a0|, где
Sцa) = |a0 - a1| + |a1 - a2| + … + |an-3 - an-2| + |an-2 - an-1| + |an-1 - a0|.

Sц(a) - это алгебраическая сумма, которая содержит каждый исходный элемент ai дважды,
и её максимальное значение равно

Sц_max = 2∑i = 0, …, k-1 (hi - bi),
где hi = bi+k, i = 0…k-1.

Это значение достигается в двух вариантах перестановок:
1) c2i ∈ h (все наибольшие элементы имеют чётные индексы);
2) c2i + 1 ∈ h (все наибольшие элементы имеют нечётные индексы).

В то же время, минимум |an-1 - a0| = bk - bk-1 достигается при размещении пары медианных
элементов на краях последовательности c.

Максимум суммы S равен
Smax = 2∑i = 0, …, k-2 (bi+k - bi) + bk-1 - bk, или

Smax = 2∑i = 0, …, k-2 (bn-1-i - bi) + bn-k - bk-1,

и достигается в тех случаях, когда последовательность с содержит наибольшие элементы
в шахматном порядке, причём медианные элементы bk-1 и bk находятся на краях последовательности.
Количество таких перестановок при попарно различных ai составляет 2(k-1)!2.



Случай n = 2k+1

Аналогичное рассмотрение показывает, что максимум S равен

Smax = 2∑i=0…k-2 (bk+2+i - bk) + bk+1 - bk-1 + max (bk+1 - bk, bk - bk-1), или

Smax = 2∑i=0…k-2 (bn-1-i - bi) + bn-k - bk-1 + max (bk+1 - bk, bk - bk-1),

и достигается в тех случаях, когда элементы с индексами больше k идут в шахматном
порядке, а на краях последовательности оказываются медианный и ближайший к нему элемент.
Количество таких перестановок при попарно различных ai не меньше, чем (k-1)!k! (если
медиана отличается от ближайших по значению соседей на одинаковую величину, то перестановок
вдвое больше).



ПРОГРАММА (C#):

    public static void T(string text, Stopwatch timer)
    {
        TimeSpan ts = timer.Elapsed;
        string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
            ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
        Console.Write(text + elapsedTime);
    }

    public static int[] FactGen(int n)
    {
        int[] fact = new int[n + 1];

        fact[0] = 1;
        for (int i = 1; i < n + 1; i++)
            fact[i] = i * fact[i - 1];

        return fact;
    }

    public static int[] PermsGenerator(int[] arr, int num, int[] fact)
    {
        int i, j, f, newind, newnum, newval, size = arr.Length;
        int[] result = new int[size];

        Array.Copy(arr, result, size);
        for (i = 0, newnum = num; i < size - 1; i++)
        {
            f = fact[size - 1 - i];
            newind = i;
            while (newnum >= f)
            {
                newind++;
                newnum -= f;
            }
            newval = result[newind];
            for (j = newind; j > i; j--)
                result[j] = result[j - 1];
            result[i] = newval;
        }

        return result;
    }

    public static int SumAbs(int[] arr)
    {
        int sum = 0, prev = arr[0];

        foreach (int value in arr)
        {
            sum += Math.Abs(value - prev);
            prev = value;
        }

        return sum;
    }

    public static int CalcOptQuant (int n)
    {
        int k = (n - 1) / 2, k2 = Math.Max(k-2, 0);
        int[] fact = FactGen(k + 2);

        return 2*fact[k] * ((n - k - k < 2) ? fact[k-1] : fact[k]);
    }

    public static int CalcMaxSum(int[] brr)
    {
        int i, size = brr.Length, k = size / 2, sum = 0;

        for (i = 0; i < k - 1; i++)
            sum += brr[size - 1 - i] - brr[i];
        sum = 2 * sum + brr[size - k] - brr[k - 1];
        if (size - 2 * k > 0) sum += Math.Max(brr[k+1] - brr[k], brr[k] - brr[k-1]);

        return sum;
    }

    public static int[] MaxArr(int[] arr, bool detprn)
    {
        int i, j, sum, smax = -1, size = arr.Length;
        int[] perm, result = new int[size], fact = FactGen(size),
            sorted = new int[size], empire = new int[size];
        Stopwatch sw = new Stopwatch();

        Console.WriteLine("\nИсходная выборка:  ");
        foreach (int value in arr)
            Console.Write(value + "  ");
        sw.Restart();
        for (i = 0; i < fact[size]; i++)
        {
            perm = PermsGenerator(arr, i, fact);
            sum = SumAbs(perm);
            if (sum > smax) {
                smax = sum;
                result = perm;
            }
        }
        if (detprn)
            Console.Write("\nЛучшие перестановки");
        for (i = 0, j = 0; i < fact[size]; i++)
        {
            perm = PermsGenerator(arr, i, fact);
            sum = SumAbs(perm);
            if (sum == smax)
            {
                j++;
                if (detprn)
                {
                    Console.Write("\n#{0}:  ", j);
                    foreach (int value in perm)
                        Console.Write(value + "  ");
                }
            }
        }
        Array.Copy(arr, sorted, size);
        Array.Sort(sorted);
        Console.WriteLine("\nОтсортированная выборка:  ");
        foreach (int value in sorted)
            Console.Write(value + "  ");
        Console.Write("\nФакт     Наибольшая сумма: {0}   Лучших перестановок: {1}" +
            "\nРасчёт   Наибольшая сумма: {2}   Лучших перестановок, не менее: {3}", 
            smax, j, CalcMaxSum(sorted), CalcOptQuant(size));
        T("\nRuntime = ", sw);
        sw.Reset();

        return result;
    }

    static void Main(string[] args)
    {
        bool binc;
        int i, j, n, nmax = 12;
        int[] arr =  new int[0];
        Random rand = new Random();

        MaxArr(new int[] { 0, 1, 2, 3, 4, 5 }, true);
        MaxArr(new int[] { 5, 1, 3, 5, 7, 9 }, true);
        MaxArr(new int[] { 0, 1, 2, 3, 4 }, true);
        MaxArr(new int[] { 0, 1, 2, 3 }, true);
        MaxArr(new int[] { 0, 1, 2 }, true);
        for (n = 3; n <= nmax; n++)
        {
            Array.Resize(ref arr, n);
            for (i = 0; i < n;)
            {
                arr[i] = rand.Next(10, 99);
                binc = true;
                for (j = 0; j < i; j++)
                    binc &= (arr[i] != arr[j]);
                if (binc)
                    i++;
            }
            MaxArr(arr, false);
        }
    }




РЕЗУЛЬТАТЫ:


Исходная выборка:
0  1  2  3  4  5
Лучшие перестановки
#1:  2  4  0  5  1  3
#2:  2  4  1  5  0  3
#3:  2  5  0  4  1  3
#4:  2  5  1  4  0  3
#5:  3  0  4  1  5  2
#6:  3  0  5  1  4  2
#7:  3  1  4  0  5  2
#8:  3  1  5  0  4  2
Отсортированная выборка:
0  1  2  3  4  5
Факт     Наибольшая сумма: 17   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 17   Лучших перестановок, не менее: 8
Runtime = 00:00:00.01
Исходная выборка:
5  1  3  5  7  9
Лучшие перестановки
#1:  5  1  7  3  9  5
#2:  5  1  9  3  7  5
#3:  5  3  7  1  9  5
#4:  5  3  9  1  7  5
#5:  5  7  1  9  3  5
#6:  5  7  3  9  1  5
#7:  5  9  1  7  3  5
#8:  5  9  3  7  1  5
#9:  5  1  7  3  9  5
#10:  5  1  9  3  7  5
#11:  5  3  7  1  9  5
#12:  5  3  9  1  7  5
#13:  5  7  1  9  3  5
#14:  5  7  3  9  1  5
#15:  5  9  1  7  3  5
#16:  5  9  3  7  1  5
Отсортированная выборка:
1  3  5  5  7  9
Факт     Наибольшая сумма: 24   Лучших перестановок: 16
Расчёт   Наибольшая сумма: 24   Лучших перестановок, не менее: 8
Runtime = 00:00:00.01
Исходная выборка:
0  1  2  3  4
Лучшие перестановки
#1:  1  3  0  4  2
#2:  1  4  0  3  2
#3:  2  0  4  1  3
#4:  2  1  4  0  3
#5:  2  3  0  4  1
#6:  2  4  0  3  1
#7:  3  0  4  1  2
#8:  3  1  4  0  2
Отсортированная выборка:
0  1  2  3  4
Факт     Наибольшая сумма: 11   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 11   Лучших перестановок, не менее: 4
Runtime = 00:00:00.01
Исходная выборка:
0  1  2  3
Лучшие перестановки
#1:  1  3  0  2
#2:  2  0  3  1
Отсортированная выборка:
0  1  2  3
Факт     Наибольшая сумма: 7   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 7   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
0  1  2
Лучшие перестановки
#1:  0  2  1
#2:  1  0  2
#3:  1  2  0
#4:  2  0  1
Отсортированная выборка:
0  1  2
Факт     Наибольшая сумма: 3   Лучших перестановок: 4
Расчёт   Наибольшая сумма: 3   Лучших перестановок, не менее: 2
Runtime = 00:00:00.01
Исходная выборка:
25  51  87
Отсортированная выборка:
25  51  87
Факт     Наибольшая сумма: 98   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 98   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
78  10  34  64
Отсортированная выборка:
10  34  64  78
Факт     Наибольшая сумма: 166   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 166   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
23  26  93  16  45
Отсортированная выборка:
16  23  26  45  93
Факт     Наибольшая сумма: 195   Лучших перестановок: 4
Расчёт   Наибольшая сумма: 195   Лучших перестановок, не менее: 4
Runtime = 00:00:00.00
Исходная выборка:
85  12  11  13  90  88
Отсортированная выборка:
11  12  13  85  88  90
Факт     Наибольшая сумма: 382   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 382   Лучших перестановок, не менее: 8
Runtime = 00:00:00.00
Исходная выборка:
82  43  28  55  29  39  18
Отсортированная выборка:
18  28  29  39  43  55  82
Факт     Наибольшая сумма: 206   Лучших перестановок: 24
Расчёт   Наибольшая сумма: 206   Лучших перестановок, не менее: 24
Runtime = 00:00:00.00
Исходная выборка:
64  20  43  89  47  94  52  71
Отсортированная выборка:
20  43  47  52  64  71  89  94
Факт     Наибольшая сумма: 300   Лучших перестановок: 72
Расчёт   Наибольшая сумма: 300   Лучших перестановок, не менее: 72
Runtime = 00:00:00.02
Исходная выборка:
45  53  81  17  76  97  26  50  51
Отсортированная выборка:
17  26  45  50  51  53  76  81  97
Факт     Наибольшая сумма: 337   Лучших перестановок: 288
Расчёт   Наибольшая сумма: 337   Лучших перестановок, не менее: 288
Runtime = 00:00:00.23
Исходная выборка:
55  51  36  12  82  63  89  58  14  22
Отсортированная выборка:
12  14  22  36  51  55  58  63  82  89
Факт     Наибольшая сумма: 420   Лучших перестановок: 1152
Расчёт   Наибольшая сумма: 420   Лучших перестановок, не менее: 1152
Runtime = 00:00:02.46
Исходная выборка:
96  95  67  49  65  69  53  78  35  55  94
Отсортированная выборка:
35  49  53  55  65  67  69  78  94  95  96
Факт     Наибольшая сумма: 348   Лучших перестановок: 11520
Расчёт   Наибольшая сумма: 348   Лучших перестановок, не менее: 5760
Runtime = 00:00:29.21
Исходная выборка:
50  43  39  64  59  18  81  16  44  12  15  77
Отсортированная выборка:
12  15  16  18  39  43  44  50  59  64  77  81
Факт     Наибольшая сумма: 463   Лучших перестановок: 28800
Расчёт   Наибольшая сумма: 463   Лучших перестановок, не менее: 28800
Runtime = 00:06:26.81




АНАЛИЗ РЕЗУЛЬТАТОВ

Во всех рассмотренных случаях тестирование полностью подтвердило предлагаемое общее
решение.


Ответ 3

Предлагаю следующий алгоритм:


Сортируем входной массив
Поочередно берем элементы с конца его первой половины и с конца его второй половины
Если длина массива нечетная, берем самый центральный элемент и помещаем его в начало
или в конец, в зависимости от того, где больше разница с ним - слева или справа


Код на C#:

static void Main(string[] args)
{
    //var input = new[] { 1, 2, 3, 4, 5 };
    //var input = new[] { 1, 2, 3, 100, 200 };
    //var input = new[] { 1, 2, 100, 200, 300 };
    //var input = new[] { 22, 26, 48, 37, 47, 13, 9, 19 };
    var input = new[] { 40, 27, 4, 9, 32, 35, 41, 39, 2 };
    var combine = GetCombine(input);
    var sum = GetSum(combine);
    Console.WriteLine(string.Join(" ", combine));
    Console.WriteLine(sum);
}

static int[] GetCombine(int[] input)
{
    var len = input.Length;
    var sorted = input.OrderBy(x => x).ToArray();
    var output = new int[len];
    var d = 0;
    if (len % 2 == 1)
    {
        if (sorted[len / 2] - sorted[len / 2 - 1] >
            sorted[len / 2 + 1] - sorted[len / 2]) d = 1;
        output[(len - 1 + d) % len] = sorted[len / 2];
    }
    for (int i = 0; i < len / 2; ++i)
    {
        output[2 * i + d] = sorted[len / 2 - 1 - i];
        output[2 * i + 1 + d] = sorted[len - 1 - i];
    }
    return output;
}

static int GetSum(int[] combine)
{
    int sum = 0;
    for (int i = 0; i < combine.Length - 1; ++i)
        sum += Math.Abs(combine[i] - combine[i + 1]);
    return sum;
}


Проверить