Рубрики

Самая длинная последовательность, такая, что разница между смежными

Учитывая массив размера n, задача состоит в том, чтобы найти самую длинную подпоследовательность, такую, чтобы разница между смежными составляла один.

Примеры:

Input :  arr[] = {10, 9, 4, 5, 4, 8, 6}
Output :  3
As longest subsequences with difference 1 are, "10, 9, 8", 
"4, 5, 4" and "4, 5, 6"

Input :  arr[] = {1, 2, 3, 2, 3, 7, 2, 1}
Output :  7
As longest consecutive sequence is "1, 2, 3, 2, 3, 2, 1"

Эта проблема основана на концепции самой длинной возрастающей проблемы подпоследовательности .

Let arr[0..n-1] be the input array and 
dp[i] be the length of the longest subsequence (with
differences one) ending at index i such that arr[i] 
is the last element of the subsequence.

Then, dp[i] can be recursively written as:
dp[i] = 1 + max(dp[j]) where 0 < j < i and 
       [arr[j] = arr[i] -1  or arr[j] = arr[i] + 1]
dp[i] = 1, if no such j exists.

To find the result for a given array, we need 
to return max(dp[i]) where 0 < i < n.

Ниже приводится реализация на основе динамического программирования. Это следует за рекурсивной структурой, обсужденной выше.

C ++

// C ++ программа для поиска самой длинной подпоследовательности, такой
// разница между соседними элементами
// подпоследовательность одна.
#include<bits/stdc++.h>

using namespace std;

  
// Функция для определения длины самой длинной подпоследовательности

int longestSubseqWithDiffOne(int arr[], int n)

{

    // Инициализируем массив dp [] с 1 как

    // один элемент будет иметь длину 1

    int dp[n];

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

        dp[i] = 1;

  

    // Начало обхода указанного массива

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

    {

        // Сравнить со всеми предыдущими элементами

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

        {

            // Если элемент является последовательным, то

            // рассмотреть эту подпоследовательность и обновить

            // dp [i], если требуется.

            if ((arr[i] == arr[j]+1) ||

                (arr[i] == arr[j]-1))

  

                dp[i] = max(dp[i], dp[j]+1);

        }

    }

  

    // Максимальная длина будет максимальным значением

    // массива дп

    int result = 1;

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

        if (result < dp[i])

            result = dp[i];

    return result;

}

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

int main()

{

    // Самая длинная подпоследовательность с одним отличием

    // {1, 2, 3, 4, 3, 2}

    int arr[] = {1, 2, 3, 4, 5, 3, 2};

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

    cout << longestSubseqWithDiffOne(arr, n);

    return 0;

}

Джава

// Java-программа для поиска самой длинной подпоследовательности
// такой, что разница между соседними
// элементы подпоследовательности - один.

import java.io.*;

  

class GFG {

      

    // Функция для определения длины самого длинного

    // подпоследовательность

    static int longestSubseqWithDiffOne(int arr[], 

                                           int n)

    {

        // Инициализируем массив dp [] с 1 как

        // один элемент будет иметь длину 1

        int dp[] = new int[n];

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

            dp[i] = 1;

  

        // Начало обхода указанного массива

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

        {

            // Сравнить со всеми предыдущими

            // элементы

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

            {

                // Если элемент является последовательным

                // затем рассмотрим эту подпоследовательность

                // и обновляем dp [i], если требуется.

                if ((arr[i] == arr[j] + 1) ||

                    (arr[i] == arr[j] - 1))

  

                dp[i] = Math.max(dp[i], dp[j]+1);

            }

        }

  

        // Максимальная длина будет максимальной

        // значение массива dp.

        int result = 1;

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

            if (result < dp[i])

                result = dp[i];

        return result;

    }

  

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

    public static void main(String[] args)

    {

        // Самая длинная подпоследовательность с одним

        // разница

        // {1, 2, 3, 4, 3, 2}

        int arr[] = {1, 2, 3, 4, 5, 3, 2};

        int n = arr.length;

        System.out.println(longestSubseqWithDiffOne(

                                           arr, n));

    }

}

  
// Этот код предоставлен Prerna Saini

питон

# Функция для определения длины самой длинной подпоследовательности

def longestSubseqWithDiffOne(arr, n):

    # Инициализировать массив dp [] с 1 как

    # один элемент будет иметь длину 1

    dp = [1 for i in range(n)]

  

    # Начать обход заданного массива

    for i in range(n):

        # Сравнить со всеми предыдущими элементами

        for j in range(i):

            # Если элемент является последовательным, то

            # рассмотреть эту подпоследовательность и обновить

            # dp [i] если требуется.

            if ((arr[i] == arr[j]+1) or (arr[i] == arr[j]-1)):

                dp[i] = max(dp[i], dp[j]+1)

  

    # Самая длинная длина будет максимальным значением

    # массива дп

    result = 1   

    for i in range(n):

        if (result < dp[i]):

            result = dp[i]

             

    return result

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

arr = [1, 2, 3, 4, 5, 3, 2]

# Самая длинная подпоследовательность с одним отличием
# {1, 2, 3, 4, 3, 2}

n = len(arr)

print longestSubseqWithDiffOne(arr, n)

  
# Этот код предоставлен Афзалом Ансари

C #

// C # программа для поиска самой длинной подпоследовательности
// такой, что разница между соседними
// элементы подпоследовательности - один.

using System;

  

class GFG {

      

    // Функция для определения длины самого длинного

    // подпоследовательность

    static int longestSubseqWithDiffOne(int []arr, 

                                           int n)

    {

          

        // Инициализируем массив dp [] с 1 как

        // один элемент будет иметь длину 1

        int []dp = new int[n];

          

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

            dp[i] = 1;

  

        // Начало обхода указанного массива

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

        {

              

            // Сравнить со всеми предыдущими

            // элементы

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

            {

                // Если элемент является последовательным

                // затем рассмотрим эту подпоследовательность

                // и обновляем dp [i], если требуется.

                if ((arr[i] == arr[j] + 1) ||

                         (arr[i] == arr[j] - 1))

  

                dp[i] = Math.Max(dp[i], dp[j]+1);

            }

        }

  

        // Максимальная длина будет максимальной

        // значение массива dp.

        int result = 1;

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

            if (result < dp[i])

                result = dp[i];

                  

        return result;

    }

  

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

    public static void Main()

    {

          

        // Самая длинная подпоследовательность с одним

        // разница

        // {1, 2, 3, 4, 3, 2}

        int []arr = {1, 2, 3, 4, 5, 3, 2};

        int n = arr.Length;

          

        Console.Write(

            longestSubseqWithDiffOne(arr, n));

    }

}

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

PHP

<?php
// PHP программа для поиска самой длинной
// подпоследовательность такая разница
// между соседними элементами
// подпоследовательность одна.

  
// Функция для определения длины
// самая длинная подпоследовательность

function longestSubseqWithDiffOne($arr, $n)

{

      

    // Инициализируем dp []

    // массив с 1 как

    // один элемент будет

    // быть 1 длины

    $dp[$n] = 0;

      

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

        $dp[$i] = 1;

  

    // Начало обхода

    // данный массив

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

    {

          

        // Сравнить со всеми

        // предыдущие элементы

        for($j = 0; $j < $i; $j++)

        {

              

            // Если элемент

            // последовательно

            // учти это

            // подпоследовательность и

            // обновляем dp [i] if

            // требуется.

            if (($arr[$i] == $arr[$j] + 1) ||

                ($arr[$i] == $arr[$j] - 1))

  

                $dp[$i] = max($dp[$i],

                         $dp[$j] + 1);

        }

    }

  

    // Самая длинная длина будет

    // максимальное значение

    // массива дп

    $result = 1;

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

        if ($result < $dp[$i])

            $result = $dp[$i];

    return $result;

}

  

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

    // Самая длинная подпоследовательность с

    // одно отличие

    // {1, 2, 3, 4, 3, 2}

    $arr = array(1, 2, 3, 4, 5, 3, 2);

    $n = sizeof($arr);

    echo longestSubseqWithDiffOne($arr, $n);

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


Выход:

6

Сложность времени: O (n 2 )
Вспомогательное пространство: O (n)

Эта статья предоставлена Сахилом Чхаброй (KILLER) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Самая длинная последовательность, такая, что разница между смежными

0.00 (0%) 0 votes