سب سے طویل بائٹونک ضمنی


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے کوڈ نیشن ڈی ای شا گوگل جے پی مورگن مائیکروسافٹ
لڑی متحرک پروگرامنگ

فرض کریں آپ کے پاس صف 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 کے طور پر شروع کریں Seeq []۔
  3. بائیں سے دائیں تک بڑھتی ہوئی سیکشن [] میں اسے ذخیرہ کرکے طویل ترین بڑھتی ہوئی تقویت کا پتہ لگائیں۔
  4. ایک صف اعلان کریں کمی دیئے گئے صف کی لمبائی کے برابر سائز کی۔
  5. دائیں سے بائیں اور گھٹتے سیکیک [] میں اسٹور کرکے سب سے طویل تخفیف شدہ حصquہ تلاش کریں۔
  6. میکس آؤٹ پٹ نامی ایک متغیر کی ابتدا کریں جس میں سکسو [0] + کمی ہوتی ہوئی سیک [0] - 1 میں میک آؤٹ پٹ کہا جاتا ہے۔
  7. زیادہ سے زیادہ معلوم کریں بڑھتی ہوئی سیکی [i] + گھٹتی ہوئی سیک [i] - 1 اور اسے میک آؤٹ پٹ میں اسٹور کریں۔
  8. واپس میکس آؤٹ پٹ.

وضاحت

سائز این کی ان پٹ صف میں مثبت عدد صحیح ہوتا ہے۔ ہم سے پوچھا جاتا ہے کہ دیئے گئے صفوں کا سب سے لمبا بٹونک ترتیب تلاش کریں۔ بٹونک ترتیب کو تسلسل کے طور پر بیان کیا جاسکتا ہے جو پہلے بڑھتا ہے ، جس کا مطلب ہے کہ ترتیب میں نمبر پہلے بڑھتا ہے۔ پھر تسلسل کے اختتام تک تعداد کم ہوجاتی ہے۔ ہمیں سب سے طویل بائونک ترتیب کی لمبائی کا تعین کرنے کی ضرورت ہے۔

پہلے حل کو دو حصوں میں الگ کریں۔ ہم نے دو ارے کا اعلان کیا ، پہلی صف کو ایک سمجھا جاتا ہے بڑھتی ہوئی سیکی سرنی۔ سب سے طویل بڑھتا ہوا تسلسل وہ ترتیب ہے جس میں بڑھتے ہوئے تسلسل میں اعداد پہلے ہونا چاہئے۔ تو ، ہم ایک گھونسے ہوئے لوپ میں صف کو عبور کرنے جارہے ہیں۔ بڑھتی تقلید کو تلاش کرتے رہیں۔ پھر ہمیں ایک ایسی حالت چیک کرنا ہوگی کہ اگر موجودہ عنصر اگلے عنصر سے کم ہے۔ اور بڑھتی ہوئی سیک کا موجودہ عنصر بڑھتی سیکیک [] کے اگلے عنصر سے بھی کم ہے۔ اگر سچ ہے تو عنصر کو بڑھتی ہوئی سیکیٹ [j] + 1 کے طور پر اسٹور کریں۔ اس میں اضافہ ہوتا ہے کیونکہ ہم اس میں صف کو پہلے ہی شروع کرچکے ہیں۔

دوسرا ، صف کا اعلان کریں ، گھٹتی ہوئی سیک []. اس گھٹتے سیکہ [] میں ، ہم سرنی کے دائیں سے بائیں سرنی کے گھسیٹے ہوئے انداز میں سرنی کو عبور کرنے جارہے ہیں۔ ہم جانچنے جارہے ہیں کہ کیا موجودہ عنصر اگلے عنصر سے زیادہ ہے۔ کیوں کہ ہم دائیں سے بائیں منتقل ہو رہے ہیں۔ اس کے بعد اسے گھٹتے ہوئے سیکیک [i] میں کم ہونے والے سیکیک [j] +1 میں اپ ڈیٹ کریں۔ کوڈ کے آخری مرحلے میں ، ہمیں زیادہ سے زیادہ بڑھتی ہوئی سیکیک [i] + کمی ہوتی سیکیک [i] - 1 تلاش کرنا ہوگی جو میکس آؤٹ پٹ میں محفوظ ہے۔

ضابطے

سب سے طویل بائٹونک سب کے لئے 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 (n)2کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے نیسڈڈ لوپ کا استعمال کیا جس کی وجہ سے یہ الگورتھم متعدد وقت میں چلتا ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے دو اضافی اشاروں کا استعمال کیا جس کا سائز ان پٹ سرنی پر منحصر ہے۔ خلائی پیچیدگی لکیری ہے۔