Առավելագույնի հասցնել շրջանաձեւ զանգվածում հաջորդական տարբերությունների գումարը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Կադենս Հնդկաստան eBay GE Healthcare Karat Quora SAP լաբորատորիաներ քառակուսի
Դասավորություն Ագահ դասավորում

Խնդիրի հայտարարություն

Ենթադրենք, որ դուք ունեք ամբողջ թիվ դասավորություն, Այս զանգվածին պետք է վերաբերվել որպես ա շրջանաձեւ զանգված, Rayանգվածի վերջին արժեքը միացված կլինի առաջին զանգվածին, աn 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 ամբողջական թվերը, Rayանգվածը պետք է վերաբերվի որպես a շրջանաձեւ զանգված որը կարելի է անցնել առաջին տարրին վերջին տարրից անմիջապես հետո: Մեզ խնդրել են պարզել հաջորդական տարրերի տարբերությունների առավելագույն գումարը: Եվ մենք առավելություն ունենք զանգվածը վերադասավորելու համար: Այնպիսին, որ մենք կարողանանք առավելագույնի հասցնել տարբերությունների հանրագումարը:

Այստեղ մենք զանգված ենք տվել: Մենք չենք պատրաստվում իրականում վերադասավորել զանգվածը, մենք կարող ենք պարզապես խաղալ նրա թվերի հետ: Այժմ մենք անցնելու ենք զանգվածի միայն կեսը: Դա զանգվածի միայն n / 2 երկարությունն է, որտեղ n զանգվածի իրական երկարությունն է: Մենք հայտարարեցինք արտադրանք կոչվող փոփոխական: Ինչը կստանա զանգվածի տարբերությունները: Եվ հետո ամփոփեք դա և պահեք այն արդյունքի համար: Բայց զանգվածը անցնելուց առաջ մենք պատրաստվում ենք զանգվածը տեսակավորել: Մենք զանգվածը դասավորելու ենք այնպես, որ այն պետք է աճի ըստ հերթականության: Դրանից հետո տեսակավորում զանգվածը, որը զանգվածում ունի ամենացածր թիվը զանգվածի սկզբում է: Իսկ զանգվածում ավելի մեծ քանակը զանգվածի վերջում է:

Քանի որ մենք դասավորել ենք զանգվածը, մենք պետք է անցնենք զանգվածը մինչ զանգվածի երկարության կեսը: Դրանից հետո մենք ստանում ենք զանգվածի և ելքային արժեքի ընթացիկ արժեքի կրկնակի տարբերություն և պահում ենք դրանք արդյունքի համար: Դրանում մենք ստանում ենք տարբերությունը, և այնուհետև ստանում ենք զանգվածի վերջին արժեքը ՝ դրա արժեքից երկու անգամ: Եվ ապա գումարեք ելքային արժեքը և պահեք այն արդյունքի մեջ: Շարունակեք այս գործընթացը մինչ զանգվածի երկարության կեսի հասնելը և վերադարձնել արդյունքի արժեքը:

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n տեղեկամատյան n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք դասավորել ենք զանգվածը: Այսպիսով, ժամանակի բարդությունը նման է միաձուլման տեսակներին: Քանի որ դա նշանակում է ժամանակի բարդության վերին սահմանը:

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: Այսպիսով, ալգորիթմի կողմից պահանջվող տիեզերական բարդությունը հաստատուն է: Բայց ամբողջ ծրագրի տիեզերական բարդությունը գծային է: