மிக நீண்ட பிட்டோனிக் பின்விளைவு


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது கோட்நேஷன் டி.இ ஷா கூகிள் ஜேபி மோர்கன் மைக்ரோசாப்ட்
அணி டைனமிக் புரோகிராமிங்

உங்களிடம் ஒரு உள்ளது என்று வைத்துக்கொள்வோம் வரிசை 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 இல் XNUMX என அனைத்து குறியீட்டு கூறுகளையும் துவக்கவும் [].
  3. இடமிருந்து வலமாக அதிகரிக்கும் சீக் [] இல் சேமிப்பதன் மூலம் மிக நீண்ட காலமாக அதிகரிக்கும் தொடர்ச்சியைக் கண்டறியவும்.
  4. ஒரு வரிசையை அறிவிக்கவும் குறைகிறதுசெக் [] கொடுக்கப்பட்ட வரிசையின் நீளத்திற்கு சமமான அளவு.
  5. வலமிருந்து இடமாகப் பயணிக்கும் மற்றும் குறைந்து வரும் செக்கில் சேமிப்பதன் மூலம் மிக நீளமாகக் குறைந்து வரும் அடுத்தடுத்ததைக் கண்டறியவும்.
  6. அதிகரிக்கும் சேக் [0] + குறைக்கும் சேக் [0] - 1 க்கு maxOutput எனப்படும் மாறியைத் தொடங்கவும்.
  7. அதிகபட்சத்தைக் கண்டறியவும் அதிகரிக்கும்செக் [i] + குறைகிறதுசெக் [i] - 1 அதை maxOutput இல் சேமிக்கவும்.
  8. திரும்பவும் அதிகபட்ச வெளியீடு.

விளக்கம்

அளவு n இன் உள்ளீட்டு வரிசை நேர்மறை முழு எண்களைக் கொண்டுள்ளது. கொடுக்கப்பட்ட வரிசையின் மிக நீளமான பிட்டோனிக் வரிசையைக் கண்டுபிடிக்க நாங்கள் கேட்கப்படுகிறோம். பிட்டோனிக் வரிசையை முதலில் அதிகரிக்கும் வரிசை என வரையறுக்கலாம், அதாவது வரிசையில் உள்ள எண்ணிக்கை முதலில் அதிகரிக்கிறது. பின்னர் வரிசை முடிவடையும் வரை எண்ணிக்கை குறைகிறது. மிக நீளமான பிட்டோனிக் வரிசையின் நீளத்தை நாம் தீர்மானிக்க வேண்டும்.

முதலில், தீர்வை இரண்டு பகுதிகளாக பிரிக்கவும். நாங்கள் இரண்டு வரிசைகளை அறிவிக்கிறோம், முதல் வரிசை ஒரு என்று கருதப்படுகிறது அதிகரிக்கும்செக் வரிசை. நீண்ட காலமாக அதிகரிக்கும் வரிசை என்பது அதிகரிக்கும் வரிசையில் எண்கள் முதலில் இருக்க வேண்டிய வரிசை. எனவே, நாம் ஒரு உள்ளமைந்த வட்டத்தில் வரிசையை கடக்கப் போகிறோம். அதிகரித்து வரும் அடுத்தடுத்ததைக் கண்டறியவும். தற்போதைய உறுப்பு அடுத்த உறுப்பை விட குறைவாக இருந்தால் ஒரு நிபந்தனையை நாம் சரிபார்க்க வேண்டும். மேலும் அதிகரிக்கும் சேக்கின் தற்போதைய உறுப்பு அதிகரிக்கும் சேக்கின் அடுத்த உறுப்பை விட குறைவாக உள்ளது []. உண்மை என்றால், உறுப்பை அதிகரிக்கும் செக் [j] + 1 என சேமிக்கவும். இது சேர்க்கிறது, ஏனெனில் நாம் ஏற்கனவே வரிசையை 1 ஆக துவக்கியுள்ளோம்.

இரண்டாவது, ஒரு வரிசையை அறிவிக்கவும், குறைகிறதுசெக் []. இந்த குறைந்து வரும் செக் [] இல், வரிசையின் வலமிருந்து இடமாக ஒரு உள்ளமைக்கப்பட்ட லூப் பாணியில் வரிசையை நாம் பயணிக்கப் போகிறோம். தற்போதைய உறுப்பு அடுத்த உறுப்பை விட அதிகமாக இருக்கிறதா என்று சோதிக்கப் போகிறோம். ஏனென்றால் நாம் வலமிருந்து இடமாக பயணிக்கிறோம். பின்னர் அதை குறைந்து வரும் சீக் [i] க்கு குறைந்து வரும் செக் [j] +1 க்கு புதுப்பிக்கவும். குறியீட்டின் கடைசி கட்டத்தில், அதிகபட்சமாக அதிகரிக்கும் அதிகபட்சம் [i] + குறைந்து வரும் சீக் [i] - 1 ஐ நாம் கண்டுபிடிக்க வேண்டும், இது அதிகபட்ச வெளியீட்டில் சேமிக்கப்படுகிறது.

குறியீடு

மிக நீண்ட பிட்டோனிக் அடுத்தடுத்த சி ++ குறியீடு

#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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்2எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. நாங்கள் ஒரு உள்ளமை வளையத்தைப் பயன்படுத்தியதால், வழிமுறை பல்லுறுப்புறுப்பு நேரத்தில் இயங்கச் செய்தது.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. உள்ளீட்டு வரிசையைப் பொறுத்து இரண்டு கூடுதல் வரிசைகளை நாங்கள் பயன்படுத்தினோம். விண்வெளி சிக்கலானது நேரியல்.