מאַקסאַמייז די סומע פון ​​קאָנסעקוטיווע דיפעראַנסיז אין אַ קייַלעכיק מענגע  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין קאַדענס ינדיאַ עבייַ גע העאַלטהקאַרע קאַראַט קוואָראַ SAP לאַבס קוואַדראַט
מענגע זשעדנע סאָרטינג

פּראָבלעם סטאַטעמענט  

רעכן איר האָבן אַן ינטעגער מענגע. דעם מענגע זאָל זיין באהאנדלט ווי אַ קייַלעכיק מענגע. די לעצטע ווערט פון אַ מענגע וועט זיין פארבונדן צו דער ערשטער מענגע, אַn ⇒ a1. דער פּראָבלעם "מאַקסאַמייז די סומע פון ​​קאָנסעקוטיווע דיפעראַנסיז אין אַ קייַלעכיק מענגע" פרעגט צו געפֿינען די מאַקסימום סומע פון ​​די חילוק צווישן יעדער קאָנסעקוטיווע עלעמענט. איר מוזן געפֿינען די חילוק צווישן אַ קאָנסעקוטיווע עלעמענט. איר האָט ערלויבט צו ריעריינדזש די מענגע נומערן. אַזאַ אַז די סומע פון ​​דיפעראַנסיז זאָל זיין מאַקסימום.

מאַקסימום סומע = | 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 איז די פאַקטיש לענג פון די מענגע. מיר האָבן דערקלערט אַ בייַטעוודיק גערופֿן רעזולטאַט. וואָס וועט באַקומען די דיפעראַנסיז פון די מענגע. און דעמאָלט סומע אַרויף און קראָם עס צו פּראָדוקציע. איידער מיר פאָרן די מענגע, מיר וועלן סאָרטירן די מענגע. מיר וועלן סאָרטירן די מענגע אַזוי אַז עס זאָל זיין אין ינקריסינג סדר. נאָך סאָרטינג די מענגע מיר האָבן אַ נומער לאָואַסט אין די מענגע איז אין די אָנהייב פון די מענגע. און די גרעסערע נומער אין די מענגע איז אין די סוף פון די מענגע.

זינט מיר האָבן אויסגעשטעלט די מענגע, מיר נאָר דאַרפֿן צו פאָרן די מענגע אַרויף צו די האַלב פון די לענג פון די מענגע. דערנאָך מיר באַקומען די חילוק פון צוויי מאָל פון די קראַנט ווערט פון די מענגע און דער רעזולטאַט ווערט און סטאָרד עס צו רעזולטאַט. אין דעם מיר באַקומען די חילוק, און דאַן באַקומען די לעצטע ווערט פון די מענגע, צוויי מאָל די ווערט. און דעריבער לייגן אַרויף די רעזולטאַט ווערט און קראָם עס אין פּראָדוקציע. האַלטן דעם פּראָצעס ביז די האַלב פון די לענג פון די מענגע איז ריטשט און צוריקקומען די ווערט פון פּראָדוקציע.

קאָדעקס  

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (n קלאָץ n) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע. ווייַל מיר האָבן אויסגעשטעלט די מענגע. אַזוי די קאַמפּלעקסיטי פון צייט איז ווי די סאָרט פון צונויפגיסן. זינט דעם מאַרקס די אויבערשטער גרענעץ פון די צייט קאַמפּלעקסיטי.

זע אויך
לאָנגעסט פּראָסט פּרעפיקס ניצן וואָרט דורך וואָרט מאַטטשינג

ספעיס קאַמפּלעקסיטי

אָ (1) ווי קיין עקסטרע פּלאַץ איז פארלאנגט. אַזוי די פּלאַץ קאַמפּלעקסיטי פארלאנגט דורך די אַלגערידאַם איז קעסיידערדיק. אָבער די פּלאַץ קאַמפּלעקסיטי פון די גאנצע פּראָגראַם איז לינעאַר.