Максимизирајте го збирот на последователни разлики во кружна низа


Ниво на тешкотија Лесно
Често прашувано во Каденс Индија eBay ГЕ здравство Карат Quora SAP лаборатории Плоштад
Низа Алчен Сортирање

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

Да претпоставиме дека имате број низа. Оваа низа треба да се третира како кружна низа. Последната вредност на низата ќе биде поврзана со првата низа, an ⇒ а1. Проблемот „Максимизирај збир на последователни разлики во кружна низа“ бара да се открие максималниот збир на разликата помеѓу секој последователен елемент. Значи, мора да ја пронајдете разликата помеѓу последователен елемент. Дозволено е да ги преуредувате броевите на низата. Таква што збирот на нивните разлики треба да биде максимум.

Максимална сума = | a1 - a2 | + | a3 - a4 | + | а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 цели броеви. Низата треба да се третира како кружна низа што може да се помине до првиот елемент директно по последниот елемент. Од нас беше побарано да ја откриеме максималната сума на разликите помеѓу последователните елементи. И ние имаме предност да ја преуредиме низата. Такво што можеме да го зголемиме збирот на разликите.

Тука дадовме низа. Ние всушност нема да ја преуредиме низата, можеме едноставно да играме со нејзините броеви. Сега ќе поминеме само половина од низата. Тоа е само до n / 2 должина на низата каде n е вистинската должина на низата. Деклариравме променлива наречена излез. Што ќе ги добие разликите во низата. И потоа сумирајте го и зачувајте го за да излезе. Но, пред да ја прелистуваме низата, ќе ја сортираме низата. Toе ја сортираме низата така што треба да биде во зголемен редослед. После сортирање низата имаме најмал број во низата е на почетокот на низата. И поголем број во низата е на крајот од низата.

Бидејќи ја сортиравме низата, треба да ја поминеме низата само до половина од должината на низата. Потоа ја добиваме разликата од двапати од сегашната вредност на низата и излезната вредност и ја чуваме на излез. Во ова ја добиваме разликата, а потоа ја добиваме последната вредност на низата, двојно поголема од нејзината вредност. И потоа додадете со излезната вредност и зачувајте ја во излез. Чувајте го овој процес вклучен додека не се достигне половина од должината на низата и вратете ја вредноста на излезот.

Код

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

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

Временска комплексност

О (н дневник н) каде „Н“ е бројот на елементи во низата. Бидејќи ја сортиравме низата. Значи, временската комплексност станува како онаа од спојување. Бидејќи тоа ја означува горната граница на временската сложеност.

Комплексноста на просторот

О (1) бидејќи не е потребен дополнителен простор. Значи, комплексноста на просторот што ја бара алгоритмот е постојана. Но, комплексноста на целата програма е линеарна.