მაქსიმალურად გაზარდეთ წრიული მასივის თანმიმდევრული სხვაობების ჯამი


Რთული ტური Easy
ხშირად ეკითხებიან კადენს ინდოეთი eBay GE Healthcare კარატი Quora SAP ლაბორატორიები Square
Array ხარბ დახარისხება

პრობლემის განცხადება

დავუშვათ, რომ თქვენ გაქვთ მთელი რიცხვი მასივი. ეს მასივი უნდა განიხილებოდეს, როგორც წრიული მასივი. მასივის ბოლო მნიშვნელობა დაუკავშირდება პირველ მასივს, ა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 რიცხვები. მასივი უნდა განიხილებოდეს, როგორც 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

სირთულის ანალიზი

დროის სირთულე

O (n log n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. რადგან მასივი დავალაგეთ. დროის სირთულე შერწყმის დალაგების მსგავსი ხდება. რადგან ეს აღნიშნავს დროის სირთულის ზედა ზღვარს.

სივრცის სირთულე

O (1) რადგან დამატებითი ადგილი არ არის საჭირო. ასე რომ, ალგორითმის მიერ მოთხოვნილი სივრცის სირთულე მუდმივია. მაგრამ მთელი პროგრამის სივრცის სირთულე ხაზოვანია.