በክብ ድርድር ውስጥ የተከታታይ ልዩነቶችን ድምር ያሳድጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ካዴንስ ህንድ eBay GE የጤና Karat Quora የ SAP ላብራቶሪዎች አራት ማዕዘን
ሰልፍ ስስታም መደርደር

የችግሩ መግለጫ

አንድ አለዎት እንበል ኢንቲጀር ደርድር. ይህ ድርድር እንደ አንድ መታከም አለበት ክብ ድርድር. የአንድ ድርድር የመጨረሻ እሴት ከመጀመሪያው ድርድር ጋር ይገናኛል ፣ ሀn ⇒ a1. በክብ ድርድር ውስጥ “የተከታታይ ልዩነቶችን ድምር ከፍ ያድርጉ” የሚለው ችግር በእያንዳንዱ ተከታታይ ንጥረ ነገር መካከል ያለውን ከፍተኛውን ድምር ለማወቅ ይጠይቃል። ስለዚህ በተከታታይ አካል መካከል ያለውን ልዩነት መፈለግ አለብዎት። የድርድር ቁጥሮችን እንደገና እንዲያስተካክሉ ተፈቅደዋል። የእነሱ ልዩነት ድምር ከፍተኛ መሆን አለበት።

ከፍተኛ ድምር = | ሀ 1 - ሀ 2 | + | 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 ትክክለኛ የድርድር ርዝመት። ውፅዓት የተባለ ተለዋዋጭ አውጀናል ፡፡ የድርድሩ ልዩነቶችን የሚያገኘው የትኛው ነው። እና ከዚያ ያንን ጠቅለል አድርገው ለውጤት ያከማቹ ፡፡ ግን ድርድርን ከማስተላለፋችን በፊት ድርድሩ እንዲደረደር እናደርጋለን። ቅደም ተከተሉን እየጨመረ በሄደ መጠን ቅደም ተከተሉን እንመድባለን ፡፡ በኋላ መደርደር እኛ በድርድሩ ውስጥ በጣም ዝቅተኛ ቁጥር ያለን ድርድር በድርድሩ መጀመሪያ ላይ ነው። እና በሰልፍ ውስጥ የሚበዛው ቁጥር በምድቡ መጨረሻ ላይ ነው።

ድርድርን ስለደረደርን ፣ ድርደራውን እስከ ድርድሩ ርዝመት ግማሽ ድረስ ማቋረጥ ብቻ ያስፈልገናል። ከዚያ አሁን ካለው የድርድር ዋጋ እና የውጤት እሴት የሁለት እጥፍ ልዩነት እናገኛለን እና ወደ ምርት እናከማቸዋለን። በዚህ ውስጥ ልዩነቱን እናገኛለን ፣ ከዚያ የድርብሩን የመጨረሻ እሴት ፣ ሁለት እጥፍ ዋጋውን እናገኛለን። እና ከዚያ ከውጤቱ እሴት ጋር ይጨምሩ እና በውጤቱ ውስጥ ያከማቹ። የድርድሩ ርዝመት ግማሽ እስከሚደርስ ድረስ ይህን ሂደት ያቆዩ እና የውጤቱን ዋጋ ይመልሱ።

ኮድ

በክብ ድርድር ውስጥ የተከታታይ ልዩነቶችን ድምር ከፍ ለማድረግ የ 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

በክብ ድርድር ውስጥ የተከታታይ ልዩነቶችን ድምር ከፍ ለማድረግ የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n log n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ምክንያቱም ድርድርን ስለደረድርነው። ስለዚህ የጊዜ ውስብስብነቱ እንደ ውህደት ዓይነት ይሆናል። ይህ የጊዜ ውስብስብነቱን የላይኛው ወሰን የሚያመለክት ስለሆነ።

የቦታ ውስብስብነት

ኦ (1) ተጨማሪ ቦታ ስለማያስፈልግ ፡፡ ስለዚህ በአልጎሪዝም የሚፈለገው የቦታ ውስብስብነት ቋሚ ነው። ግን የመላው መርሃግብር የቦታ ውስብስብነት መስመራዊ ነው ፡፡