အရှည်ဆုံး Bitonic နောက်ဆက်တွဲ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် CodeNation DE Shaw Google JP Morgan Microsoft က
အခင်းအကျင်း Dynamic Programming

မင်းမှာတစ်ခုရှိတယ်ဆိုပါစို့ အခင်းအကျင်း of ကိန်းဂဏန်းများ အဆိုပါပြproblemနာကိုကြေညာချက်အရှည်ဆုံး bitonic နောက်ဆက်တွဲထွက်ရှာရန်မေးတယ်။ တစ်ခုချင်းစီ၏ bitonic sequence ကိုပထမ ဦး ဆုံးတိုးမြှင့်ပြီးတော့လျော့နည်းစေသည့် sequence ကိုအဖြစ်ထည့်သွင်းစဉ်းစားသည်။

နမူနာ

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

ရှင်းလင်းချက်

1 4 76 78 54 32 ၂၃ (ပထမ ဦး ဆုံး ၇၈ အထိမြှောက်ပြီး ၂၃ အထိလျှော့ချပါ။

အရှည်ဆုံး Bitonic နောက်ဆက်တွဲ

 

algorithm

  1. array တစ်ခုကိုကြေငြာပါ IncreaseSeq [] ပေးထားသောခင်းကျင်းအရှည်၏အရှည်ကဲ့သို့တူညီသောအရွယ်အစား၏။
  2. indexs element များအားလုံးကို createSeq created array ၏ 1 အဖြစ်စတင်ပါ။
  3. ဘယ်ဘက်မှညာသို့ IncreaseSeq [] တွင်သိမ်းဆည်းခြင်းဖြင့်အရှည်ဆုံးဆက်တိုက်တိုးမှုကိုရှာဖွေပါ။
  4. array တစ်ခုကိုကြေငြာပါ decreasingSeq [] ပေးထားသောခင်းကျင်း၏အရှည်ကဲ့သို့တူညီသောအရွယ်အစား၏။
  5. လက်ျာမှဘယ်သို့အရှည်ကြာဆုံးကျဆင်းနေသောနောက်ဆက်တွဲရှာပါ။ ၎င်းကို decreasingSeq သို့သိမ်းဆည်းပါ။
  6. increaseSeq [0] + decreasingSeq [0] သို့ maxOutput ဟုခေါ်သည့် variable ကိုစတင်ပါ - 1 ။
  7. အများဆုံးရှာပါ increaseSeq [i] + decreasingSeq [i] - ၁ နှင့် maxOutput မှသိမ်းထားပါ။
  8. ပြန်လာ maxOutput.

ရှင်းလင်းချက်

အရွယ်အစား n ၏ input ခင်းကျင်းမှုမှာအပေါင်းကိန်းများပါ ၀ င်သည်။ ပေးထားသောခင်းကျင်းမှု၏အရှည်ဆုံး bitonic sequence ကိုရှာဖွေရန်ကျွန်ုပ်တို့အားတောင်းဆိုသည်။ အဆိုပါ bitonic sequence ကိုပထမ ဦး ဆုံးတိုးမြှင့်သော sequence ကိုအဖြစ်သတ်မှတ်နိုင်ပါသည်, ထို sequence ကိုပထမ ဦး ဆုံးတိုးအတွက်နံပါတ်ကိုဆိုလိုသည်။ ထိုအခါအရေအတွက်က sequence ကို၏အဆုံးသည်အထိလျော့နည်းစေသည်။ ကျနော်တို့အရှည်ဆုံး bitonic sequence ကို၏အရှည်ကိုဆုံးဖြတ်ရန်လိုအပ်သည်။

ပထမ ဦး စွာအဖြေကိုနှစ်ပိုင်းခွဲပါ။ Array နှစ်ခုကြေငြာသည်။ ပထမ array ကိုစဉ်းစားသည် တိုးလာသည် array ။ အရှည်ဆုံးတိုးမြှင့်သောအစီအစဉ်သည်နံပါတ်များကိုတိုးပွားလာသော sequence တွင်ပထမနေရာတွင်ထားသင့်သည့်အစီအစဉ်ဖြစ်သည်။ ဒါကြောင့်ကျနော်တို့က nested loop ထဲမှာ array ကိုဖြတ်သန်းသွားမယ်။ ဆက်လက်တိုးမြှင့်နောက်ဆက်တွဲရှာဖွေတာအပေါ်ထားပါ။ ထို့နောက်ကျွန်ုပ်တို့သည်လက်ရှိ element သည်လာမည့် element ထက်လျော့နည်းလျှင်အခြေအနေကိုစစ်ဆေးရပါမည်။ ထို့အပြင် increaseSeq ၏လက်ရှိဒြပ်စင်သည်နောက်ထပ်တိုးမြှင့်နေသောSeq [] ထက်နည်းသည်။ true ရှိလျှင် element ကို raisingSeq [j] + 1. အနေဖြင့်သိမ်းဆည်းပါ။ ၎င်းကို array ထဲတွင် 1 အဖြစ်အစပြုထားပြီးဖြစ်သောကြောင့်၎င်းသည်ထပ်ပေါင်းထည့်သည်။

ဒုတိယအချက်မှာ array တစ်ခုကိုကြေငြာပါ။ decreasingSeq [] ။ ဤ decreasingSeq [] တွင်ကျွန်ုပ်တို့သည် array ကို nested loop fashion ဖြင့်ညာဘက်မှဘယ်ဘက်သို့သွားလိမ့်မည်။ ကျနော်တို့ကလက်ရှိဒြပ်စင်လာမည့်ဒြပ်စင်ထက်သာ။ ကြီးမြတ်ရှိမရှိစစ်ဆေးသွားနေကြသည်။ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာညာဘက်ကနေဘယ်ဘက်ကိုဖြတ်သန်းနေလို့ပဲ။ ပြီးရင်အဲဒါကို decreasingSeq [i] to decreasingSeq [j] +1 ကို update လုပ်ပါ။ ကုဒ်၏နောက်ဆုံးအဆင့်တွင် maxOutput တွင်သိုလှောင်ထားသည့် 1 အမြင့်ဆုံး sseq [i] + decreasingSeq [i] - XNUMX ကိုရှာရန်လိုအပ်သည်။

ကုဒ်

အရှည်ဆုံး Bitonic နောက်ဆက်တွဲများအတွက် 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

အရှည်ဆုံး Bitonic နောက်ဆက်တွဲများအတွက် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (။2ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ polynomial အချိန်တွင် algorithm ကို run စေသော nested loop တစ်ခုကိုကျွန်ုပ်တို့အသုံးပြုခဲ့သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျနော်တို့ကအဘယ်သူ၏အရွယ်အစား input ကိုခင်းကျင်းအပေါ်မူတည်သည်နှစ်ခုအပို Array ကိုအသုံးပြုကတည်းက။ အဆိုပါအာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။