Увећајте збир узастопних разлика у кружном низу  


Ниво тешкоће Лако
Често питани у Цаденце Индиа еБаи ГЕ Хеалтхцаре карат Куора САП Лабс Квадрат
Ред Похлепан сортирање

Изјава о проблему  

Претпоставимо да имате цео број поредак. Овај низ треба третирати као кружни низ. Последња вредност низа биће повезана са првим низом, аn ⇒ а1. Проблем „Максимизирање збира узастопних разлика у кружном низу“ тражи да се сазна максимални збир разлике између сваког узастопног елемента. Дакле, морате пронаћи разлику између узастопног елемента. Дозвољено вам је да преуредите бројеве низа. Такав да збир њихових разлика треба да буде максималан.

Максимални збир = | а1 - а2 | + | а3 - а4 | + | аn-1 - аn |. | + | аn - а1 |

Пример  

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 интегерс. Низ треба третирати као а кружни низ која се може прећи до првог елемента непосредно након последњег елемента. Од нас је затражено да сазнамо максимални збир разлика између узастопних елемената. И ми имамо предност у преуређивању низа. Такав да можемо максимизирати збир разлика.

Види такође
Изоморфне жице Леетцоде решење

Овде смо дали низ. Нећемо заправо преуређивати низ, можемо се једноставно играти с његовим бројевима. Сада ћемо прећи само половину низа. То је само до н / 2 дужине низа, где је н стварна дужина низа. Прогласили смо променљиву која се назива излаз. Што ће добити разлике у низу. А онда сумирајте то и сачувајте га за излаз. Али пре него што пређемо низ, сортираћемо низ. Сортираћемо низ тако да буде у све већем редоследу. После сортинг низ који имамо најнижи број у низу налази се на почетку низа. А већи број у низу налази се на крају низа.

С обзиром да смо сортирали низ, треба да пређемо низ до половине дужине низа. Тада добијамо разлику од двоструке тренутне вредности низа и излазне вредности и складиштимо је на излаз. У томе добијамо разлику, а затим добијамо последњу вредност низа, двоструко већу од његове вредности. А онда збројите излазну вредност и сачувајте је у излазној вредности. Држите овај процес док се не достигне половина дужине низа и вратите вредност излаза.

код  

Ц ++ код за максимизирање збира узастопних разлика у кружном низу

#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

Јава код за максимизирање зброја узастопних разлика у кружном низу

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

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

Сложеност времена

О (н лог н) где „Н“ је број елемената у низу. Јер смо сортирали низ. Тако временска сложеност постаје као код спајања. Пошто то означава горњу границу временске сложености.

Види такође
Најдужи уобичајени префикс помоћу подударања речи по речи

Сложеност простора

О (1) јер није потребан додатни простор. Дакле, сложеност простора коју захтева алгоритам је константна. Али свемирска сложеност читавог програма је линеарна.