Рубрики

Построение самой длинной возрастающей подпоследовательности (N log N)

Массивы

В моем предыдущем посте я подробно объяснил проблему увеличения длины подпоследовательности (LIS). Тем не менее, публикация покрывала только код, связанный с запросом размера LIS, но не конструкцию LIS. Я оставил это как упражнение. Если вы решили, ура. Если нет, вы не одиноки, вот код.

Если вы еще не читали мой предыдущий пост, читайте здесь . Обратите внимание, что приведенный ниже код печатает LIS в обратном порядке. Мы можем изменить порядок печати, используя стек (явный или системный стек). Я оставляю объяснение как упражнение (легко).

C ++

// Реализация C ++, чтобы найти самую длинную возрастающую подпоследовательность
// за O (n Log n) время.
#include <bits/stdc++.h>

using namespace std;

  
// Бинарный поиск

int GetCeilIndex(int arr[], vector<int>& T, int l, int r,

                 int key)

{

    while (r - l > 1) {

        int m = l + (r - l) / 2;

        if (arr[T[m]] >= key)

            r = m;

        else

            l = m;

    }

  

    return r;

}

  

int LongestIncreasingSubsequence(int arr[], int n)

{

    // Добавить граничный случай, когда массив n равен нулю

    // Зависим от умных указателей

  

    vector<int> tailIndices(n, 0); // Инициализируется с 0

    vector<int> prevIndices(n, -1); // инициализируется с -1

  

    int len = 1; // он всегда будет указывать на пустое место

    for (int i = 1; i < n; i++) {

        if (arr[i] < arr[tailIndices[0]]) {

            // новое наименьшее значение

            tailIndices[0] = i;

        }

        else if (arr[i] > arr[tailIndices[len - 1]]) {

            // arr [i] хочет расширить наибольшую подпоследовательность

            prevIndices[i] = tailIndices[len - 1];

            tailIndices[len++] = i;

        }

        else {

            // arr [i] хочет быть потенциальным партнером

            // будущая подпоследовательность

            // Он заменит значение ceil в tailIndices

            int pos = GetCeilIndex(arr, tailIndices, -1,

                                   len - 1, arr[i]);

  

            prevIndices[i] = tailIndices[pos - 1];

            tailIndices[pos] = i;

        }

    }

  

    cout << "LIS of given input" << endl;

    for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i])

        cout << arr[i] << " ";

    cout << endl;

  

    return len;

}

  

int main()

{

    int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    printf("LIS size %d\n", LongestIncreasingSubsequence(arr, n));

  

    return 0;

}

Джава

// Реализация Java, чтобы найти самый длинный
// увеличиваем подпоследовательность в O (n Log n)
// время

import java.util.Arrays;

  

class GFG {

  

    // Бинарный поиск

    static int GetCeilIndex(int arr[],

                            int T[], int l,

                            int r, int key)

    {

  

        while (r - l > 1) {

  

            int m = l + (r - l) / 2;

            if (arr[T[m]] >= key)

                r = m;

            else

                l = m;

        }

  

        return r;

    }

  

    static int LongestIncreasingSubsequence(

        int arr[], int n)

    {

  

        // Добавить граничный случай, когда массив n равен нулю

        // Зависим от умных указателей

  

        int tailIndices[] = new int[n];

  

        // Инициализируется с 0

        Arrays.fill(tailIndices, 0);

  

        int prevIndices[] = new int[n];

  

        // инициализируется с -1

        Arrays.fill(prevIndices, -1);

  

        // он всегда будет указывать на пустой

        // место расположения

        int len = 1;

  

        for (int i = 1; i < n; i++) {

            if (arr[i] < arr[tailIndices[0]])

  

                // новое наименьшее значение

                tailIndices[0] = i;

  

            else if (arr[i] > arr[tailIndices[len - 1]]) {

  

                // arr [i] хочет расширить

                // самая большая подпоследовательность

                prevIndices[i] = tailIndices[len - 1];

                tailIndices[len++] = i;

            }

            else {

  

                // arr [i] хочет быть потенциальным

                // условие будущей подпоследовательности

                // Он заменит значение ceil в

                // tailIndices

                int pos = GetCeilIndex(arr,

                                       tailIndices, -1, len - 1, arr[i]);

  

                prevIndices[i] = tailIndices[pos - 1];

                tailIndices[pos] = i;

            }

        }

  

        System.out.println("LIS of given input");

  

        for (int i = tailIndices[len - 1]; i >= 0;

             i = prevIndices[i])

            System.out.print(arr[i] + " ");

  

        System.out.println();

  

        return len;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

        int n = arr.length;

  

        System.out.print("LIS size\n" + LongestIncreasingSubsequence(arr, n));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Реализация Python для
# найти наибольшее увеличение
# подпоследовательность
# за O (n Log n) время.

  
# Бинарный поиск

def GetCeilIndex(arr, T, l, r, key):

  

    while (r - l > 1):

      

        m = l + (r - l)//2

        if (arr[T[m]] >= key):

            r = m

        else:

            l = m

  

    return r

   

def LongestIncreasingSubsequence(arr, n):

  

    # Добавить граничный регистр,

    # когда массив n равен нулю

    # Зависит от умных указателей

      

    # Инициализировано с 0

    tailIndices =[0 for i in range(n + 1)]  

  

    # Инициализировано с -1

    prevIndices =[-1 for i in range(n + 1)]  

      

    # это всегда будет указывать

    # в пустое место

    len = 1 

    for i in range(1, n):

      

        if (arr[i] < arr[tailIndices[0]]):

          

            # новое наименьшее значение

            tailIndices[0] = i

          

        elif (arr[i] > arr[tailIndices[len-1]]):

          

            # arr [i] хочет расширить

            # наибольшая подпоследовательность

            prevIndices[i] = tailIndices[len-1]

            tailIndices[len] = i

            len += 1

          

        else:

          

            # arr [i] хочет быть

            # потенциальное состояние

            # будущая подпоследовательность

            # Это заменит ceil

            # значение в tailIndices

            pos = GetCeilIndex(arr, tailIndices, -1,

                                   len-1, arr[i])

   

            prevIndices[i] = tailIndices[pos-1]

            tailIndices[pos] = i

          

    print("LIS of given input")

    i = tailIndices[len-1]

    while(i >= 0):

        print(arr[i], " ", end ="")

        i = prevIndices[i]

    print()

   

    return len

  
# код водителя

arr = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ]

n = len(arr)

   

print("LIS size\n", LongestIncreasingSubsequence(arr, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// реализация C #, чтобы найти самый длинный
// увеличиваем подпоследовательность в O (n Log n)
// время

using System;

  

class GFG {

  

    // Бинарный поиск

    static int GetCeilIndex(int[] arr, int[] T, int l,

                            int r, int key)

    {

  

        while (r - l > 1) {

            int m = l + (r - l) / 2;

  

            if (arr[T[m]] >= key)

                r = m;

            else

                l = m;

        }

  

        return r;

    }

  

    static int LongestIncreasingSubsequence(

        int[] arr, int n)

    {

  

        // Добавить граничный случай, когда массив n равен нулю

        // Зависим от умных указателей

  

        int[] tailIndices = new int[n];

  

        // Инициализируется с 0

        for (int i = 0; i < n; i++)

            tailIndices[i] = 0;

  

        int[] prevIndices = new int[n];

  

        // инициализируется с -1

        for (int i = 0; i < n; i++)

            prevIndices[i] = -1;

  

        // он всегда будет указывать на пустой

        // место расположения

        int len = 1;

  

        for (int i = 1; i < n; i++) {

            if (arr[i] < arr[tailIndices[0]])

  

                // новое наименьшее значение

                tailIndices[0] = i;

  

            else if (arr[i] > arr[tailIndices[len - 1]]) {

  

                // arr [i] хочет расширить

                // самая большая подпоследовательность

                prevIndices[i] = tailIndices[len - 1];

                tailIndices[len++] = i;

            }

            else {

  

                // arr [i] хочет быть потенциальным

                // условие будущей подпоследовательности

                // Он заменит значение ceil в

                // tailIndices

                int pos = GetCeilIndex(arr,

                                       tailIndices, -1, len - 1, arr[i]);

  

                prevIndices[i] = tailIndices[pos - 1];

                tailIndices[pos] = i;

            }

        }

  

        Console.Write("LIS of given input");

  

        for (int i = tailIndices[len - 1]; i >= 0;

             i = prevIndices[i])

            Console.Write(arr[i] + " ");

  

        Console.WriteLine();

  

        return len;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

        int n = arr.Length;

  

        Console.Write("LIS size\n" + LongestIncreasingSubsequence(arr, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Реализация PHP, чтобы найти наибольшее увеличение
// подпоследовательность за O (n Log n) времени.

  
// Бинарный поиск

function GetCeilIndex($arr, $T, $l, $r, $key)

{

    while ($r - $l > 1)

    {

        $m = (int)($l + ($r - $l)/2);

        if ($arr[$T[$m]] >= $key)

            $r = $m;

        else

            $l = $m;

    }

  

    return $r;

}

  

function LongestIncreasingSubsequence($arr, $n)

{

    // Добавить граничный случай, когда массив n равен нулю

    // Зависим от умных указателей

  

    $tailIndices=array_fill(0, $n+1, 0); // Инициализируется с 0

    $prevIndices=array_fill(0, $n+1, -1); // инициализируется с -1

  

    $len = 1; // он всегда будет указывать на пустое место

    for ($i = 1; $i < $n; $i++)

    {

        if ($arr[$i] < $arr[$tailIndices[0]])

        {

            // новое наименьшее значение

            $tailIndices[0] = $i;

        }

        else if ($arr[$i] > $arr[$tailIndices[$len-1]])

        {

            // arr [i] хочет расширить наибольшую подпоследовательность

            $prevIndices[$i] = $tailIndices[$len-1];

            $tailIndices[$len++] = $i;

        }

        else

        {

            // arr [i] хочет быть потенциальным партнером

            // будущая подпоследовательность

            // Он заменит значение ceil в tailIndices

            $pos = GetCeilIndex($arr, $tailIndices, -1,

                                $len-1, $arr[$i]);

  

            $prevIndices[$i] = $tailIndices[$pos-1];

            $tailIndices[$pos] = $i;

        }

    }

  

    echo "LIS of given input\n";

    for ($i = $tailIndices[$len-1]; $i >= 0; $i = $prevIndices[$i])

        echo $arr[$i]." ";

    echo "\n";

  

    return $len;

}

  
// Код драйвера

$arr = array( 2, 5, 3, 7, 11, 8, 10, 13, 6 );

$n = count($arr);

  

print("LIS size ".LongestIncreasingSubsequence($arr, $n));

  
// Этот код предоставлен chandan_jnu
?>


Выход:

LIS of given input
13 10 8 7 3 2 
LIS size 6

Упражнения:

1. Вы знаете алгоритм Кадане , чтобы найти подмассив с максимальной суммой . Измените алгоритм Кадане для отслеживания начального и конечного местоположения подмассива максимальной суммы.

2. Измените алгоритм Кадане , чтобы найти подмассив с максимальной суммой в круговом массиве. Обратитесь на форум GFG за множеством комментариев по этому вопросу.

3. Даны два целых числа A и B в качестве входных данных. Найдите число чисел Фибоначчи, существующих между этими двумя числами (включая A и B). Например, A = 3 и B = 18, между {3, 5, 8, 13} есть 4 числа Фибоначчи. Сделайте это за время O (log K), где K max (A, B). Каково ваше наблюдение?

— Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Построение самой длинной возрастающей подпоследовательности (N log N)

0.00 (0%) 0 votes