Максимизируйте сумму последовательных различий в круговом массиве


Сложный уровень Легко
Часто спрашивают в Cadence Индия eBay GE Healthcare карат Quora SAP Labs Квадратный
массив Жадный Сортировка

Постановка задачи

Предположим, у вас есть целое массив. Этот массив следует рассматривать как круговой массив. Последнее значение массива будет связано с первым массивом, an ⇒ a1. Задача «Максимизировать сумму последовательных разностей в круговом массиве» просит определить максимальную сумму разностей между каждым последовательным элементом. Итак, вам нужно найти разницу между последовательным элементом. Вы можете переставлять номера массива. Такой, чтобы сумма их различий была максимальной.

Максимальная сумма = | a1 - a2 | + | a3 - a4 | + | аn-1 - аn | + | аn - a1 |

Пример

arr[]={9, 8, 4, 2}
22

объяснение

Мы можем расположить данный массив как 9, 2, 8, 4, тогда он даст

| 9 - 2 | + | 2-8 | + | 8 - 4 | + | 4 - 9 | = 22

Максимизируйте сумму последовательных различий в круговом массиве

Алгоритм

1. Set a variable output to 0.
2. Sort the given array.
3. Traverse up to n/2 length of the array(n is the length of the array).
    1. Sum up the value of output and array’s last values and store it to sum.
    2. Get the difference of output and twice of array’s starting value and store it to the output.
4. Return the value of output.

объяснение

Учитывая массив of целые. Массив следует рассматривать как круговой массив который можно перейти к первому элементу сразу после последнего элемента. Нас попросили определить максимальную сумму различий между последовательными элементами. И у нас есть преимущество переставить массив. Таким образом, мы можем максимизировать сумму различий.

Здесь мы дали массив. Фактически мы не собираемся переупорядочивать массив, мы можем просто поиграть с его числами. Теперь мы собираемся пройти только половину массива. Это только до n / 2 длины массива, где n - фактическая длина массива. Мы объявили переменную с именем output. Которая получит различия в массиве. А затем суммируйте это и сохраните для вывода. Но перед тем, как пройти по массиву, мы собираемся отсортировать массив. Мы собираемся отсортировать массив в порядке возрастания. После сортировка массив, у нас есть самый низкий номер в массиве, находится в начале массива. И большее число в массиве находится в конце массива.

Поскольку мы отсортировали массив, нам нужно пройти только до половины длины массива. Затем мы получаем двойную разницу между текущим значением массива и выходным значением и сохраняем его для вывода. В этом мы получаем разницу, а затем получаем последнее значение массива, вдвое превышающее его значение. А затем сложите с выходным значением и сохраните его в выходных данных. Продолжайте этот процесс до тех пор, пока не будет достигнута половина длины массива, и верните значение вывода.

Код:

Код C ++ для максимизации суммы последовательных различий в круговом массиве

#include<iostream>
#include<algorithm>

using namespace std;

int getMaxDiff(int arr[], int n)
{
    int output = 0;

    sort(arr, arr + n);

    for (int i = 0; i < n/2; i++)
    {
        output -= (2 * arr[i]);
        output += (2 * arr[n - i - 1]);
    }

    return output;
}
int main()
{
    int arr[] = { 9, 8, 2, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaxDiff(arr, n) << endl;
    return 0;
}
22

Код Java для максимизации суммы последовательных различий в круговом массиве

import java.util.Arrays;

class maximumDiff
{
    public static int getMaxDiff(int arr[], int n)
    {
        int output = 0;

        Arrays.sort(arr);

        for (int i = 0; i < n/2; i++)
        {
            output -= (2 * arr[i]);
            output += (2 * arr[n - i - 1]);
        }

        return output;
    }
    public static void main (String[] args)
    {
        int arr[] = {9, 8, 2, 4 };
        int n = arr.length;
        System.out.println(getMaxDiff(arr, n));
    }
}
22

Анализ сложности

Сложность времени

O (п войти п) в котором «Н» - количество элементов в массиве. Потому что мы отсортировали массив. Таким образом, временная сложность становится похожей на сортировку слиянием. Поскольку это означает верхнюю границу временной сложности.

Космическая сложность

O (1) так как дополнительное пространство не требуется. Таким образом, сложность пространства, необходимая для алгоритма, постоянна. Но пространственная сложность всей программы линейна.