Збільшити суму послідовних різниць у круговому масиві


Рівень складності Легко
Часто запитують у Каденс Індія eBay GE Healthcare Karat Quora SAP Labs Площа
масив Жадібний Сортування

Постановка проблеми

Припустимо, у вас є ціле масив. Цей масив слід розглядати як a круговий масив. Останнє значення масиву буде підключено до першого масиву, an ⇒ a1. Завдання «Максимізувати суму послідовних різниць у круговому масиві» вимагає з’ясувати максимальну суму різниці між кожним послідовним елементом. Тож вам доведеться знайти різницю між послідовними елементами. Вам дозволено переставляти номери масивів. Такі, що сума їх відмінностей повинна бути максимальною.

Максимальна сума = | a1 - a2 | + | а3 - а4 | + | an-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 цілих чисел. Масив слід розглядати як a круговий масив який можна перейти до першого елемента безпосередньо після останнього елемента. Нас попросили з’ясувати максимальну суму різниць між послідовними елементами. І ми маємо перевагу переставити масив. Така, що ми можемо максимізувати суму різниць.

Тут ми дали масив. Ми фактично не збираємося переставляти масив, ми можемо просто пограти з його номерами. Зараз ми збираємось пройти лише половину масиву. Це лише до n / 2 довжини масиву, де n - фактична довжина масиву. Ми оголосили змінну, яка називається output. Що збирається отримати відмінності масиву. А потім підсумуйте це і збережіть для виведення. Але перед обходом масиву ми збираємося сортувати масив. Ми збираємося сортувати масив таким чином, щоб він мав зростати. Після сортування масив, у якого ми маємо найнижче число в масиві, знаходиться на початку масиву. І більша кількість масиву знаходиться в кінці масиву.

Оскільки ми відсортували масив, нам потрібно пройти масив лише до половини довжини масиву. Тоді ми отримуємо різницю вдвічі поточного значення масиву та вихідного значення і зберігаємо його на виході. У цьому ми отримуємо різницю, а потім отримуємо останнє значення масиву, подвоєне його значення. А потім складіть вихідне значення і збережіть його у вихідному. Тримайте цей процес до тих пір, поки не буде досягнуто половини довжини масиву, і поверніть значення виводу.

код

Код С ++ для максимізації суми послідовних різниць у круговому масиві

#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 (n журнал n) де "N" - кількість елементів у масиві. Тому що ми відсортували масив. Тож складність часу стає такою, як у злиття. Оскільки це позначає верхню межу часової складності.

Складність простору

O (1) оскільки додатковий простір не потрібен. Отже, складність простору, яку вимагає алгоритм, постійна. Але космічна складність усієї програми є лінійною.