לאָנגעסט ביטאָניק סאַבסאַקוואַנס


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

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

בייַשפּיל

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

דערקלערונג

1 4 76 78 54 32 23 (ערשטער ינקריסינג אַרויף צו 78 און דאַן רידוסינג ביז 23.

לאָנגעסט ביטאָניק סאַבסאַקוואַנס

 

אַלגאָריטהם

  1. דערקלערן אַ מענגע ינקריסינגסעק [] ווי די לענג פון די געגעבן מענגע לענג.
  2. יניטיאַליזירן אַלע די ינדאַסיז עלעמענטן ווי 1 פון באשאפן מענגע ינקריסינגסעק [].
  3. געפינען אויס די לאָנגעסט ינקריסינג סאַבסטאַנסאַז דורך סטאָרינג עס אין די ינקריסינגסעק [] פון לינקס צו רעכטס.
  4. דערקלערן אַ מענגע דעקרעאַסינגעק [] די גרייס די זעלבע ווי די לענג פון די געגעבן מענגע.
  5. געפֿינען די לאָנגעסט דיקריסינג סאַבסטאַנסאַז טראַווערסינג פֿון רעכט צו לינקס און דורך סטאָרינג עס אין די דיקריסינג סעק [].
  6. יניטיאַליזירן אַ בייַטעוודיק גערופֿן מאַקסאָוטפּוט צו ינקריסינגעק [0] + דיקריסינגעק [0] - 1.
  7. געפינען אויס די מאַקסימום פון ינקריסינגעק [איך] + דיקריסינגעק [איך] - 1 און קראָם עס צו maxOutput.
  8. צוריקקומען די maxOutput.

דערקלערונג

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

ערשטער, באַזונדער די לייזונג אין צוויי-טיילן. מיר דערקלערן צוויי ערייז, דער ערשטער מענגע איז באטראכט ווי אַן ינקריסינגסעק מענגע. די לאָנגעסט ינקריסינג סיקוואַנס איז די סיקוואַנס אין וואָס די נומערן זאָל זיין ערשטער אין אַ ינקריסינג סיקוואַנס. מיר וועלן פאָרן די מענגע אין אַ נעסטעד שלייף. פאָרזעצן צו געפֿינען ינקריסינג סאַבסטאַנסאַז. דערנאָך מיר מוזן קאָנטראָלירן אַ צושטאַנד אַז אויב די קראַנט עלעמענט איז ווייניקער ווי דער ווייַטער עלעמענט און אויך די ינקריסינגעק ס קראַנט עלעמענט איז ווייניקער ווי דער ווייַטער עלעמענט פון ינקריסינגסעק []. אויב אמת, קראָם דעם עלעמענט ווי ינקריסינג Seq [j] + 1. דאָס מוסיף ווייַל מיר האָבן שוין ינישאַלייזד די מענגע ווי 1 אין עס.

צווייטנס, דערקלערן אַ מענגע, דעקרעאַסינגעק []. אין דעם דעקרעאַסינגעק [], מיר וועלן אַריבער די מענגע אין אַ נעסטעד שלייף מאָדע, פֿון רעכטס צו לינקס פון די מענגע. מיר וועלן קאָנטראָלירן צי די קראַנט עלעמענט איז גרעסער ווי דער ווייַטער עלעמענט. ווייַל מיר זענען אַריבער פון רעכט צו לינקס. דערהייַנטיקן עס צו די דיקריסינג Seq [i] צו די DecreasingSeq [j] +1. אין די לעצטע שריט פון דעם קאָד, מיר דאַרפֿן צו געפֿינען די מאַקסימום פון ינקריסינג Seq [i] + decreasingSeq [i] - 1 וואָס איז סטאָרד אין maxOutput.

קאָדעקס

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

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

Java קאָד פֿאַר לאָנגעסט ביטאָניק סאַבסאַקוואַנס

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

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

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

אָ (n2ווו “N” איז די נומער פון עלעמענטן אין די מענגע. זינט מיר געוויינט אַ נעסטעד שלייף וואָס אַלאַוז די אַלגערידאַם לויפן אין פּאָלינאָמיאַל צייט.

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

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