Най-дългата битонна последователност


Ниво на трудност Трудно
Често задавани в CodeNation DE Шоу Google JP Morgan Microsoft
Array Динамично програмиране

Да предположим, че имате масив of цели числа, изявлението на проблема иска да се открие най-дългата битонна подпоследователност. Битоничната последователност на масив се счита за последователност, която първо се увеличава, а след това намалява.

Пример

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

Обяснение

1 4 76 78 54 32 23 (Първо увеличаване до 78 и след това намаляване до 23.

Най-дългата битонна последователност

 

алгоритъм

  1. Декларирайте масив увеличаванеSeq [] с размер, същият като дължината на дадената дължина на масива.
  2. Инициализирайте всички елементи на индекси като 1 от създадения масив, който увеличаваSeq [].
  3. Открийте най-продължителната нарастваща подпоследователност, като я съхранявате в нарастващата последователност [] отляво надясно.
  4. Декларирайте масив decreasingSeq [] с размер, същият като дължината на дадения масив.
  5. Намерете най-дълго намаляващата подпоследователност, преминаваща отдясно наляво и като я съхранявате в намаляващата последователност [].
  6. Инициализирайте променлива, наречена maxOutput, за увеличаванеSeq [0] + decreasingSeq [0] - 1.
  7. Разберете максимума от увеличаванеSeq [i] + намаляване на Seq [i] - 1 и го съхранявайте в maxOutput.
  8. Върнете maxOutput.

Обяснение

Входният масив с размер n се състои от положителни цели числа. От нас се иска да открием най-дългата битонна последователност на дадения масив. Битоничната последователност може да бъде определена като последователността, която се увеличава първа, което означава, че броят в последователността първо се увеличава. След това броят намалява до края на последователността. Трябва да определим дължината на най-дългата битонна последователност.

Първо, разделете разтвора на две части. Декларираме два масива, първият масив се счита за увеличаванеСл масив. Най-дълго нарастващата последователност е последователността, в която числата трябва да са първи в нарастваща последователност. И така, ще преминем през масива в вложен цикъл. Продължавайте да намирате нарастваща последователност. След това трябва да проверим условие, че ако текущият елемент е по-малък от следващия елемент. И също така текущият елемент на нарастващия Seq е по-малък от следващия елемент на увеличаващия се []. Ако е вярно, съхранявайте елемента като увеличениеSeq [j] + 1. Това се добавя, защото вече сме инициализирали масива като 1 в него.

Второ, декларирайте масив, decreasingSeq []. В този decreasingSeq [] ще преминем по масива по вложен цикъл, отдясно наляво на масива. Ще проверим дали текущият елемент е по-голям от следващия елемент. Защото се движим отдясно наляво. След това го актуализирайте до decreasingSeq [i] до decreasingSeq [j] +1. В последната стъпка от кода трябва да намерим максимума за увеличаванеSeq [i] + decreasingSeq [i] - 1, който се съхранява в maxOutput.

код

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

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където "н" е броят на елементите в масива. Тъй като използвахме вложен цикъл, който накара алгоритъма да работи за полиномиално време.

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Тъй като използвахме два допълнителни масива, чийто размер зависи от входния масив. Сложността на пространството е линейна.