Самая доўгая бітонная паслядоўнасць


Узровень складанасці Жорсткі
Часта пытаюцца ў CodeNation DE Шоу Google 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 створанага масіва павялічваючы Seq [].
  3. Даведайцеся, якая самая доўгая паслядоўнасць павялічваецца, захоўваючы яе ў нарастаючым Seq [] злева направа.
  4. Абвясціце масіў decreasingSeq [] памерам, роўным даўжыні дадзенага масіва.
  5. Знайдзіце самую працяглую памяншальную паслядоўнасць, якая перасякае справа налева, і захоўваючы яе ў памяншальнай Seq [].
  6. Ініцыялізаваць зменную, якая называецца maxOutput, павялічыцьSeq [0] + decreasingSeq [0] - 1.
  7. Даведайцеся максімум павелічэннеSeq [i] + змяншэнне Seq [i] - 1 і захавайце яго ў maxOutput.
  8. Вярнуць maxOutput.

Тлумачэнне

Уваходны масіў памеру n складаецца з дадатных цэлых лікаў. Нас просяць даведацца самую доўгую бітанічную паслядоўнасць дадзенага масіва. Бітанічную паслядоўнасць можна вызначыць як паслядоўнасць, якая павялічваецца першай, што азначае, што колькасць у паслядоўнасці першай павялічваецца. Потым колькасць памяншаецца да канца паслядоўнасці. Нам трэба вызначыць даўжыню самай доўгай бітанічнай паслядоўнасці.

Спачатку раздзеліце раствор на дзве часткі. Мы аб'яўляем два масівы, першы масіў разглядаецца як павелічэннепал масіў. Самая доўгая павелічальная паслядоўнасць - гэта паслядоўнасць, пры якой лічбы павінны быць першымі ў павялічанай паслядоўнасці. Такім чынам, мы збіраемся прайсціся па масіве ва ўкладзеным цыкле. Працягвайце знаходзіць усё большую паслядоўнасць. Тады мы павінны праверыць умову, калі бягучы элемент менш наступнага элемента. А таксама бягучы элемент, які павялічваецца, меншы, чым наступны элемент, які павялічваецца, []. Калі ісціна, захоўваеце элемент як павялічваючы 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дзе "П" - колькасць элементаў у масіве. Так як мы выкарыстоўвалі ўкладзены цыкл, які прымусіў алгарытм працаваць у мнагачленны час.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Так як мы выкарыстоўвалі два дадатковыя масівы, памер якіх залежыць ад уваходнага масіва. Складанасць касмічнай прасторы лінейная.