పొడవైన బిటోనిక్ తరువాత


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది కోడ్‌నేషన్ డిఇ షా గూగుల్ జెపి మోర్గాన్ మైక్రోసాఫ్ట్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

మీకు ఒక ఉందని అనుకుందాం అమరిక 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. యొక్క గరిష్టాన్ని కనుగొనండి పెరుగుతున్నసెక్ [i] + తగ్గుతున్న సీక్ [i] - 1 మరియు దాన్ని maxOutput కు నిల్వ చేయండి.
  8. తిరిగి maxOutput.

వివరణ

పరిమాణం 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” శ్రేణిలోని మూలకాల సంఖ్య. మేము రెండు అదనపు శ్రేణులను ఉపయోగించాము, దీని పరిమాణం ఇన్పుట్ శ్రేణిపై ఆధారపడి ఉంటుంది. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.