ਸਭ ਤੋਂ ਲੰਬਾ ਬਿਟੋਨਿਕ ਉਪ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੋਡਨੇਸ਼ਨ ਡੀਈ ਸ਼ਾ ਗੂਗਲ JP Morgan Microsoft ਦੇ
ਅਰੇ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਮੰਨ ਲਓ ਤੁਹਾਡੇ ਕੋਲ ਏ ਐਰੇ 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 ਅਤੇ ਇਸਨੂੰ ਮੈਕਸ ਆਉਟਪੁੱਟ ਤੇ ਸਟੋਰ ਕਰੋ.
  8. ਵਾਪਸ ਕਰੋ ਅਧਿਕਤਮ.

ਕਥਾ

ਆਕਾਰ n ਦੀ ਇੰਪੁੱਟ ਐਰੇ ਵਿੱਚ ਸਕਾਰਾਤਮਕ ਪੂਰਨ ਅੰਕ ਸ਼ਾਮਲ ਹੁੰਦੇ ਹਨ. ਸਾਨੂੰ ਦਿੱਤੀ ਗਈ ਐਰੇ ਦਾ ਸਭ ਤੋਂ ਲੰਬਾ ਬਿਟੋਨਿਕ ਕ੍ਰਮ ਪਤਾ ਕਰਨ ਲਈ ਕਿਹਾ ਜਾਂਦਾ ਹੈ. ਬਿਟੋਨਿਕ ਕ੍ਰਮ ਨੂੰ ਪਰਿਭਾਸ਼ਾ ਦੇ ਤੌਰ ਤੇ ਪਰਿਭਾਸ਼ਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ ਜੋ ਪਹਿਲਾਂ ਵੱਧਦਾ ਹੈ, ਜਿਸਦਾ ਅਰਥ ਹੈ ਕਿ ਕ੍ਰਮ ਵਿੱਚ ਪਹਿਲਾਂ ਨੰਬਰ ਵੱਧਦਾ ਹੈ. ਤਦ ਕ੍ਰਮ ਦੇ ਅੰਤ ਤੱਕ ਗਿਣਤੀ ਘੱਟ ਜਾਂਦੀ ਹੈ. ਸਾਨੂੰ ਸਭ ਤੋਂ ਲੰਬੇ ਬਿਟੋਨਿਕ ਲੜੀ ਦੀ ਲੰਬਾਈ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਪਹਿਲਾਂ, ਘੋਲ ਨੂੰ ਦੋ ਹਿੱਸਿਆਂ ਵਿਚ ਵੱਖ ਕਰੋ. ਅਸੀਂ ਦੋ ਐਰੇ ਘੋਸ਼ਿਤ ਕਰਦੇ ਹਾਂ, ਪਹਿਲੀ ਐਰੇ ਨੂੰ ਇੱਕ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ ਵਾਧਾ ਐਰੇ. ਸਭ ਤੋਂ ਲੰਬਾ ਵਧਣ ਵਾਲਾ ਕ੍ਰਮ ਉਹ ਤਰਤੀਬ ਹੈ ਜਿਸ ਵਿੱਚ ਵੱਧਦੇ ਕ੍ਰਮ ਵਿੱਚ ਨੰਬਰ ਪਹਿਲਾਂ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ. ਤਾਂ ਅਸੀ ਇੱਕ ਨੇਸਟਡ ਲੂਪ ਵਿੱਚ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ. ਵੱਧ ਰਹੀ ਅਨੁਸਾਰੀਤਾ ਨੂੰ ਲੱਭਦੇ ਰਹੋ. ਫਿਰ ਸਾਨੂੰ ਇਕ ਸ਼ਰਤ ਦੀ ਜਾਂਚ ਕਰਨੀ ਪਏਗੀ ਕਿ ਜੇ ਮੌਜੂਦਾ ਤੱਤ ਅਗਲੇ ਤੱਤ ਨਾਲੋਂ ਘੱਟ ਹੈ. ਅਤੇ ਨਾਲ ਹੀ ਵੱਧ ਰਹੀ ਸੇਕ ਦਾ ਮੌਜੂਦਾ ਤੱਤ ਵੀ ਵੱਧ ਰਹੇ ਸੇਕ [] ਦੇ ਅਗਲੇ ਤੱਤ ਨਾਲੋਂ ਘੱਟ ਹੈ. ਜੇ ਸਹੀ ਹੈ ਤਾਂ ਤੱਤ ਨੂੰ ਵਧ ਰਹੇ ਸੇਕ [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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ2ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਨੇਸਟਡ ਲੂਪ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਜਿਸ ਨਾਲ ਐਲਗੋਰਿਦਮ ਨੂੰ ਬਹੁ-ਵਕਤ ਦੇ ਸਮੇਂ ਵਿਚ ਚਲਾਇਆ ਜਾਂਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਦੋ ਵਾਧੂ ਐਰੇ ਵਰਤੇ ਹਨ ਜਿਨ੍ਹਾਂ ਦਾ ਆਕਾਰ ਇਨਪੁਟ ਐਰੇ 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਲੀਨੀਅਰ ਹੈ.