לענג פון דעם גרעסטן סובאַררייַ מיט קאַנטיגיואַס עלעמענטן  


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

די פּראָבלעם "די לענג פון די גרעסטע סובאַרראַי מיט קאַנטיגיואַס עלעמענטן" שטאַטן אַז איר באַקומען אַן ינטעגער מענגע. די פּראָבלעם ויסזאָגונג איז געבעטן צו געפֿינען די לענג פון די לאָנגעסט קאַנטיגיואַס סאַב-מענגע פון ​​וואָס עלעמענטן קענען זיין עריינדזשד אין אַ סיקוואַנס (קעסיידערדיק, צו שטייַגן אָדער אַראָפּגיין) די נומערן אין די מענגע קענען פּאַסירן קייפל מאָל.

בייַשפּיל  

לענג פון דעם גרעסטן סובאַררייַ מיט קאַנטיגיואַס עלעמענטן

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

דערקלערונג

די נומער סטאַרטינג פון די 0 אינדעקס צו די 3 אינדעקס כּולל נומערן 10, 12, 13, 11 וואָס קענען זיין עריינדזשד אויף אַ שטייגער 10, 11, 12, 13 פון וואָס די לענג ווערט 4.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

דערקלערונג

די נומער סטאַרטינג פון 1 אינדעקס צו 3 אינדעקס כּולל נומערן 1, 3, 2 וואָס קענען זיין עריינדזשד אין אַ שטייגער 1, 2, 3 פון וואָס לענג ווערט 3.

אַלגאָריטהם  

  1. שטעלן maxLength צו קסנומקס.
  2. עפֿן אַ שלייף, איך = 0, בשעת איך <ל -1,
    1. דערקלערן א שטעלן און לייגן אַרר [i] אין די סעט.
    2. שטעלן די ווערט פון maxlen און מינלען צו אַרר [איך].
    3. עפֿענען אַ שלייף, סטאַרטינג פון j = i + 1, בשעת j <l,
      1. קאָנטראָלירן צי סעט איז די ווערט פון אַרר [j],
        1. אויב אמת, ברעכן.
        2. אלזא,
          1. לייג די אַרר [j] אין באַשטעטיקט.
          2. געפֿינען אויס די מינימום צווישן מינלען און אַרר [j] און קראָם עס צו מינלען.
          3. געפֿינען זיך די מאַקסימום צווישן מאַקסלען און אַרר [j] און סטאָרד עס צו מאַקסלען.
          4. קוק אויב מאַקסלען-מין = = דזש - איך
            1. אויב אמת, געפֿינען די מאַקסימום צווישן maxLength און max-minlen +1 און סטאָרד עס צו maxLength.
  3. צוריקקומען מאַקסלענגטה.
זע אויך
ציילן קוואַדרופּאַלז פון פיר סאָרטירט ערייז וועמענס סומע איז גלייַך צו אַ געגעבן ווערט x

דערקלערונג

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

לאָמיר באַטראַכטן אַ ביישפּיל:

בייַשפּיל

Arr [] = {10, 12, 13, 11, 8, 10}

מיר וועלן נוצן אַ באַשטעטיק נאָך עפן אַ שלייף און לייגן דעם נומער, יעדער אין איין, און שטעלן די ווערט פון מאַקסלען און מינלען צו אַרר [איך]. דערנאָך עפֿענען אַ נעסטעד שלייף סטאַרטינג פון איין עלעמענט איידער די קראַנט עלעמענט, ווייַל מיר האָבן שוין ינסערטאַד דעם קראַנט עלעמענט אין באַשטעטיקט. קוק אויב באַשטעטיקט כּולל די ווערט פון אַרר [דזש], אויב דער עלעמענט איז געפֿונען, ברעכן. אַנדערש אַרייַן די ווערט פון אַרר [j] אין באַשטעטיקט און געפינען אויס די מאַקסימום צווישן מאַקסלען און אַרר [j], און אויך מינימום צווישן מינלען און אַרר [j] און סטאָרד עס צו מאַקסלען און מינלען ריספּעקטיוולי. קאָנטראָלירן אויב maxlen-min איז גלייַך צו ji, און דערהייַנטיקן די ווערט פון maxLength.

maxLength = 1.

i = 0, mySet = {10}, מינלען = 10, maxlen = 10

j = i + 1 = 1, אויב mySet וועט האָבן 12, איז פאַלש,

אַזוי אַרייַן 12 אין mySet און געפֿינען די מאַקסימום פון 12 און 10 און מינימום פון און קראָם 12 אין מאַקסלען און 10 אין מינלען און קאָנטראָלירן אויב maxlen-minlen איז גלייַך צו j - i, אָבער עס איז פאַלש.

j = 2, אויב mySet וועט האָבן 13, איז פאַלש,

אַזוי אַרייַן 13 אין mySet און געפֿינען די מאַקסימום פון 13 און 12 און קראָם 13 אין מאַקסלען און 10 אין מינלען און טשעק אויב מאַקסלען-מינלען איז גלייַך צו j - איך איז פאַלש.

זע אויך
סמאָלאַסט עלעמענט ריפּיטיד פּונקט ק Times

j = 3, אויב mySet וועט האָבן 11, איז פאַלש,

אַזוי אַרייַן 11 אין mySet און געפֿינען די מאַקסימום פון 11 און 10 און קראָם 13 אין מאַקסלען און 10 אין מינלען און טשעק אויב מאַקסלען-מינלען איז גלייַך צו דזש - איך איז איצט רעכט ווייַל 13-10 איז גלייַך צו 3-0. אַזוי דערהייַנטיקן די maxLength דורך די מאַקסימום לענג און maxlen-minlen + 1 max (1, 13-10 + 1), און עס איז געפֿונען אַז 4 און 4 איז סטאָרד אין די maxLength און עס וועט פאָרזעצן צו אַריבערפירן די מענגע און שטעלן ביז עס געפינט די לענגער לענג ווי דעם פון קאַנטיגיואַס סאַב-מענגע.

רעזולטאַט: 4

קאָדעקס  

C ++ קאָד צו געפֿינען די לענג פון די גרעסטע סובאַררייַ מיט קאַנטיגיואַס עלעמענטן

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

ז'אבא קאָד צו געפֿינען די לענג פון די גרעסטע סובאַררייַ מיט קאַנטיגיואַס עלעמענטן

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

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

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

אָ (n2) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

זע אויך
געפֿינען דופּליקאַטן אין אַ געגעבן מענגע ווען עלעמענטן זענען נישט לימיטעד צו אַ קייט

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

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.