המשך הביטוני הארוך ביותר


רמת קושי קשה
נשאל לעתים קרובות CodeNation דה שו Google JP מורגן מיקרוסופט
מערך תכנות דינמי

נניח שיש לך מערך 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 במערך שנוצר הגדלת Seq [].
  3. גלה את ההמשך המתארך הארוך ביותר על ידי אחסנתו ב- הגדלת מילה [] משמאל לימין.
  4. הכריז על מערך decreasingSeq [] בגודל זהה לאורך המערך הנתון.
  5. מצא את המשך הפחתה הארוך ביותר שעובר מימין לשמאל ועל ידי אחסונו בסקירה המפחיתה [].
  6. ראשית את המשתנה הנקרא maxOutput ל- growingSeq [0] + decreasingSeq [0] - 1.
  7. גלה את המקסימום של הגדלת Seq [i] + decreasingSeq [i] - 1 ולאחסן אותו ל- maxOutput.
  8. להחזיר את maxOutput.

הסבר

מערך הקלט בגודל n מורכב ממספרים שלמים חיוביים. אנו מתבקשים לברר את הרצף הביטוני הארוך ביותר של המערך הנתון. ניתן להגדיר את הרצף הביטוני כרצף שגדל ראשון, כלומר המספר ברצף גדל תחילה. ואז המספר יורד עד סוף הרצף. עלינו לקבוע את אורך הרצף הביטוני הארוך ביותר.

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

שנית, הכריז על מערך, decreasingSeq []. בסקירה המופחתת הזו [] אנו הולכים לחצות את המערך בצורה של לולאה מקוננת, מימין לשמאל מהמערך. אנו הולכים לבדוק אם האלמנט הנוכחי גדול מהאלמנט הבא. כי אנחנו עוברים מימין לשמאל. ואז עדכן אותו ל- decreasingSeq [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

קוד ג'אווה להמשך ביטוני הארוך ביותר

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

ניתוח מורכבות

מורכבות זמן

O (n2איפה "N" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו בלולאה מקוננת שגרמה לאלגוריתם לפעול בזמן פולינומי.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו בשני מערכים נוספים שגודלם תלוי במערך הקלט. מורכבות החלל היא לינארית.