Рубрики

Самая длинная зигзагообразная подпоследовательность

Самая длинная проблема подпоследовательности зигзага состоит в том, чтобы найти длину самой длинной подпоследовательности данной последовательности так, чтобы все ее элементы чередовались.
Если последовательность {x1, x2, .. xn} является чередующейся последовательностью, то ее элемент удовлетворяет одному из следующих соотношений:

  x1 < x2 > x3 < x4 > x5 < …. xn or 
  x1 > x2 < x3 > x4 < x5 > …. xn 

Примеры :

Input: arr[] = {1, 5, 4}
Output: 3
The whole arrays is of the form  x1 < x2 > x3 

Input: arr[] = {1, 4, 5}
Output: 2
All subsequences of length 2 are either of the form 
x1 < x2; or x1 > x2

Input: arr[] = {10, 22, 9, 33, 49, 50, 31, 60}
Output: 6
The subsequences {10, 22, 9, 33, 31, 60} or
{10, 22, 9, 49, 31, 60} or {10, 22, 9, 50, 31, 60}
are longest Zig-Zag of length 6.

Эта проблема является продолжением самой длинной возрастающей проблемы подпоследовательности , но требует большего размышления для нахождения оптимального свойства субструктуры в этом.

Мы решим эту проблему методом динамического программирования. Пусть A задан массив длиной n целых чисел. Определим двумерный массив Z [n] [2] так, чтобы Z [i] [0] содержал самую длинную подпоследовательность Zig-Zag, заканчивающуюся индексом i, а последний элемент больше, чем его предыдущий элемент, а Z [i] [1] содержит самый длинный Зигзагообразная подпоследовательность, заканчивающаяся индексом i и последним элементом, меньше, чем его предыдущий элемент, тогда мы имеем следующее рекуррентное соотношение между ними,

Z[i][0] = Length of the longest Zig-Zag subsequence 
          ending at index i and last element is greater
          than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence 
          ending at index i and last element is smaller
          than its previous element

Recursive Formulation:
   Z[i][0] = max (Z[i][0], Z[j][1] + 1); 
             for all j < i and A[j] < A[i] 
   Z[i][1] = max (Z[i][1], Z[j][0] + 1); 
             for all j < i and A[j] > A[i]

Первое рекуррентное отношение основано на том факте, что, если мы находимся в позиции i, и этот элемент должен быть больше, чем его предыдущий элемент, то для того, чтобы эта последовательность (до i) была больше, мы попытаемся выбрать элемент j (<i) так что A [j] <A [i], т.е. A [j] может стать предыдущим элементом A [i], а Z [j] [1] + 1 больше, чем Z [i] [0], тогда мы обновим Z [я] [0].
Помните, что мы выбрали Z [j] [1] + 1, а не Z [j] [0] + 1, чтобы удовлетворить альтернативное свойство, потому что в Z [j] [0] последний элемент больше предыдущего, и A [i] равен больше, чем A [j], что нарушит альтернативное свойство, если мы обновим. Таким образом, вышеупомянутый факт выводит первое рекуррентное отношение, аналогичный аргумент может быть сделан и для второго рекуррентного отношения

С

// C программа для поиска самой длинной последовательности Zig-Zag в
// массив
#include <stdio.h>
#include <stdlib.h>

  
// функция, возвращающая максимум двух чисел

int max(int a, int b) {  return (a > b) ? a : b; }

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

int zzis(int arr[], int n)

{

    / * Z [i] [0] = Длина самой длинной подпоследовательности зигзага

          заканчивающийся индексом i и последний элемент больше

          чем его предыдущий элемент

     Z [i] [1] = длина самой длинной подпоследовательности зигзага

          заканчивающийся индексом i и последний элемент меньше

          чем его предыдущий элемент * /

    int Z[n][2];

  

    / * Инициализировать все значения от 1 * /

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

        Z[i][0] = Z[i][1] = 1;

  

    int res = 1; // Инициализировать результат

  

    / * Рассчитать значения снизу вверх * /

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

    {

        // Рассмотрим все элементы как предыдущие arr [i]

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

        {

            // Если arr [i] больше, то проверяем с Z [j] [1]

            if (arr[j] < arr[i] && Z[i][0] < Z[j][1] + 1)

                Z[i][0] = Z[j][1] + 1;

  

            // Если arr [i] меньше, то проверяем с помощью Z [j] [0]

            if( arr[j] > arr[i] && Z[i][1] < Z[j][0] + 1)

                Z[i][1] = Z[j][0] + 1;

        }

  

        / * Выберите максимум обоих значений по индексу i * /

        if (res < max(Z[i][0], Z[i][1]))

            res = max(Z[i][0], Z[i][1]);

    }

  

    return res;

}

  
/ * Драйвер программы * /

int main()

{

    int arr[] = { 10, 22, 9, 33, 49, 50, 31, 60 };

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

    printf("Length of Longest Zig-Zag subsequence is %d\n",

            zzis(arr, n) );

    return 0;

}

Джава

// Java программа для поиска самой длинной
// Зигзагообразная подпоследовательность в массиве

import java.io.*;

  

class GFG {

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

static int zzis(int arr[], int n)

{

    / * Z [i] [0] = Длина самого длинного

        Зигзагообразная подпоследовательность, заканчивающаяся в

        Индекс I и последний элемент

        больше, чем его предыдущий элемент

    Z [i] [1] = длина самого длинного

        Зигзагообразная подпоследовательность, заканчивающаяся в

        Индекс I и последний элемент

        меньше, чем его предыдущий

        элемент * /

    int Z[][] = new int[n][2];

  

    / * Инициализировать все значения от 1 * /

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

        Z[i][0] = Z[i][1] = 1;

  

    int res = 1; // Инициализировать результат

  

    / * Рассчитать значения снизу вверх * /

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

    {

        // Рассмотрим все элементы как

        // предыдущий из arr [i]

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

        {

            // Если arr [i] больше, то

            // проверяем с помощью Z [j] [1]

            if (arr[j] < arr[i] && 

                Z[i][0] < Z[j][1] + 1)

                Z[i][0] = Z[j][1] + 1;

  

            // Если arr [i] меньше, то

            // проверяем с помощью Z [j] [0]

            if( arr[j] > arr[i] &&

              Z[i][1] < Z[j][0] + 1)

                Z[i][1] = Z[j][0] + 1;

        }

  

        / * Выберите максимум обоих значений в

        индекс я * /

        if (res < Math.max(Z[i][0], Z[i][1]))

            res = Math.max(Z[i][0], Z[i][1]);

    }

  

    return res;

}

  
/ * Драйвер программы * /

public static void main(String[] args)

{

    int arr[] = { 10, 22, 9, 33, 49

                  50, 31, 60 };

    int n = arr.length;

    System.out.println("Length of Longest "+

                    "Zig-Zag subsequence is " +

                    zzis(arr, n));

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

python3

# Python3 программа для поиска самой длинной
# Зигзагообразная подпоследовательность в массиве

  
# Функция для возврата максимум двух чисел

  
# Функция для возврата дольше
# Длина зигзагообразной подпоследовательности

def zzis(arr, n):

      

    '' 'Z [i] [0] = Длина самой длинной подпоследовательности зигзаг

        заканчивающийся индексом i и последний элемент больше

        чем его предыдущий элемент

    Z [i] [1] = длина самой длинной подпоследовательности зигзага

        заканчивающийся индексом i и последний элемент меньше

        чем его предыдущий элемент

    Z = [[1 for i in range(2)] for i in range(n)]

  

  

    res = 1 # Инициализировать результат

  

    # Вычислять значения в порядке снизу вверх '' '

    for i in range(1, n):

          

        # Рассмотрим все элементы как предыдущие arr [i]

        for j in range(i):

  

            # Если arr [i] больше, проверьте с помощью Z [j] [1]

            if (arr[j] < arr[i] and Z[i][0] < Z[j][1] + 1):

                Z[i][0] = Z[j][1] + 1

  

            # Если arr [i] меньше, проверьте с помощью Z [j] [0]

            if( arr[j] > arr[i] and Z[i][1] < Z[j][0] + 1):

                Z[i][1] = Z[j][0] + 1

  

        # Выберите максимум обоих значений по индексу i '' '

        if (res < max(Z[i][0], Z[i][1])):

            res = max(Z[i][0], Z[i][1])

  

    return res

  
Код водителя

arr = [10, 22, 9, 33, 49, 50, 31, 60]

n = len(arr)

print("Length of Longest Zig-Zag subsequence is",

                                    zzis(arr, n))

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # программа для поиска самой длинной
// Зигзагообразная подпоследовательность в массиве

using System;

  

class GFG

{

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

static int zzis(int []arr, int n)

{

    / * Z [i] [0] = Длина самого длинного

        Зигзагообразная подпоследовательность, заканчивающаяся в

        Индекс I и последний элемент

        больше, чем его предыдущий элемент

    Z [i] [1] = длина самого длинного

        Зигзагообразная подпоследовательность, заканчивающаяся в

        Индекс I и последний элемент

        меньше, чем его предыдущий

        элемент * /

    int [,]Z = new int[n, 2];

  

    / * Инициализировать все значения от 1 * /

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

        Z[i, 0] = Z[i, 1] = 1;

  

    // Инициализировать результат

    int res = 1; 

  

    / * Вычислить значения в

    снизу вверх * /

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

    {

        // Рассмотрим все элементы как

        // предыдущий из arr [i]

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

        {

            // Если arr [i] больше, то

            // проверяем с помощью Z [j] [1]

            if (arr[j] < arr[i] && 

                Z[i, 0] < Z[j, 1] + 1)

                Z[i, 0] = Z[j, 1] + 1;

                  

            // Если arr [i] меньше, то

            // проверяем с помощью Z [j] [0]

            if( arr[j] > arr[i] &&

            Z[i, 1] < Z[j, 0] + 1)

                Z[i, 1] = Z[j, 0] + 1;

        }

  

        / * Выберите максимум обоих значений в

        индекс я * /

        if (res < Math.Max(Z[i, 0], Z[i, 1]))

            res = Math.Max(Z[i, 0], Z[i, 1]);

    }

  

    return res;

}

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

static public void Main ()

{

    int []arr = {10, 22, 9, 33, 

                 49, 50, 31, 60};

    int n = arr.Length;

    Console.WriteLine("Length of Longest "+

                      "Zig-Zag subsequence is " +

                                   zzis(arr, n));

    }

}

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

PHP

<?php
// PHP программа для поиска самого длинного зигзага
// подпоследовательность в массиве

  
// функция, возвращающая максимум двух чисел

function  maxD($a, $b) {

    return ($a > $b) ? $a : $b;

    }

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

function  zzis($arr, $n)

{

    / * Z [i] [0] = Длина самой длинной подпоследовательности зигзага

        заканчивающийся индексом i и последний элемент больше

        чем его предыдущий элемент

    Z [i] [1] = длина самой длинной подпоследовательности зигзага

        заканчивающийся индексом i и последний элемент меньше

        чем его предыдущий элемент * /

     // $ Z [$ п] [2];

  

    / * Инициализировать все значения от 1 * /

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

        $Z[$i][0] = $Z[$i][1] = 1;

  

     $res = 1; // Инициализировать результат

  

    / * Рассчитать значения снизу вверх * /

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

    {

        // Рассмотрим все элементы как предыдущие arr [i]

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

        {

            // Если arr [i] больше, то проверяем с Z [j] [1]

            if ($arr[$j] < $arr[$i] && $Z[$i][0] < $Z[$j][1] + 1)

                $Z[$i][0] = $Z[$j][1] + 1;

  

            // Если arr [i] меньше, то проверяем с помощью Z [j] [0]

            if( $arr[$j] > $arr[$i] && $Z[$i][1] < $Z[$j][0] + 1)

                $Z[$i][1] = $Z[$j][0] + 1;

        }

  

        / * Выберите максимум обоих значений по индексу i * /

        if ($res < max($Z[$i][0], $Z[$i][1]))

            $res = max($Z[$i][0], $Z[$i][1]);

    }

  

    return $res;

}

  
/ * Драйвер программы * /

  

     $arr = array( 10, 22, 9, 33, 49, 50, 31, 60 );

    $n = sizeof($arr);

    echo "Length of Longest Zig-Zag subsequence is ",

            zzis($arr, $n) ;

    echo "\n";

  

  

  
#This code is contributed by aj_36
?>


Выход :

Length of Longest Zig-Zag subsequence is 6

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

Лучший подход с временной сложностью O (n) объясняется ниже:
Пусть последовательность будет сохранена в несортированном целочисленном массиве arr [N].
Мы продолжим сравнивать математические знаки (отрицательные или положительные) разности двух последовательных элементов обр. Чтобы достичь этого, мы будем хранить знак (arr [i] — arr [i-1]) в переменной, впоследствии сравнивая его со знаком (arr [i + 1] — arr [i]). Если это не так, мы будем увеличивать наш результат. Для проверки знака мы будем использовать простую функцию Signum , которая будет определять знак переданного ей числа. То есть,

Учитывая тот факт, что мы просматриваем последовательность только один раз, это становится решением O (n) .

Алгоритм для подхода, рассмотренного выше:

Input integer array seq[N].
Initialize integer lastSign to 0. 
FOR i in range 1 to N - 1
    integer sign = signum(seq[i] - seq[i-1])
    IF sign != lastSign AND IF sign != 0
        increment length by 1. lastSign = sign.
    END IF
END FOR
return length.

Ниже приводится реализация вышеуказанного подхода:

C ++

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

/ * Программа CPP, чтобы найти максимальную длину зигзагообразной подпоследовательности
в заданной последовательности * /

int signum(int n); // прототип функции.

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

int maxZigZag(int seq[], int n)

{

    if (n == 0)

    {

        return 0;

    }

      

    int lastSign = 0, length = 1;

                    // длина инициализируется до 1, так как это минимальное значение

                    // для произвольной последовательности.

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

    {

        int Sign = signum(seq[i] - seq[i-1]);

          

        if (Sign != lastSign && Sign != 0) // это соответствует

        {

            lastSign = Sign;   // обновляем lastSign

            length++;

        }

    }

return length;    

}

  
/ * Функция Signum:
Возвращает 1, когда передано положительное целое число
Возвращает -1, когда передано отрицательное целое число
Возвращает 0 при прохождении 0. * /

int signum(int n)

{

    if (n != 0)

    {

        return n > 0 ? 1 : -1;

    }

          

    else

    {

        return 0;

    

}
// Метод драйвера

int main()

{

    int sequence1[4] = {1, 3 ,6, 2};

    int sequence2[5] = {5, 0, 3, 1, 0};

          

    int n1 = sizeof(sequence1) / sizeof(*sequence1);  // размер последовательностей

    int n2 = sizeof(sequence2) / sizeof(*sequence2);

          

    int maxLength1 = maxZigZag(sequence1,n1);

    int maxLength2 = maxZigZag(sequence2,n2); // вызов функции

          

     cout << "The maximum length of zig-zag sub-sequence in first sequence is: " << maxLength1;

     cout << endl;

    cout << "The maximum length of zig-zag sub-sequence in second sequence is: " << maxLength2;    

}

Джава

// Java-код для определения максимальной длины зигзагообразной подпоследовательности
// в заданной последовательности

class zigZagMaxLength

{

    // Метод драйвера

    public static void main(String[] args)

    {

        int[] sequence1 = {1, 3 ,6, 2};

        int[] sequence2 = {5, 0, 3, 1, 0};

          

        int n1 = sequence1.length;  // размер последовательностей

        int n2 = sequence2.length;

          

        int maxLength1 = maxZigZag(sequence1,n1);

        int maxLength2 = maxZigZag(sequence2,n2); // вызов функции

          

        System.out.println("The maximum length of zig-zag sub-sequence in first sequence is: " + maxLength1);

       System.out.println("The maximum length of zig-zag sub-sequence in second sequence is: " + maxLength2);

    }

      

    / * Функция для расчета максимальной длины зигзага

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

    * /

      

    static int maxZigZag(int[] seq, int n)

    {

        if (n == 0

        {

            return 0;

        

          

        int lastSign = 0 , length = 1

                    // длина инициализируется до 1, так как это минимальное значение

                    // для произвольной последовательности.

                                                                      

          

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

        {         

            int Sign = signum(seq[i] - seq[i-1]);

              

            if (Sign != 0 && Sign!= lastSign) // это соответствует

            {

                lastSign = Sign;         // обновляем lastSign

                length++;                     

            }         

        }

          

        return length;

    }

      

      

    / * Функция Signum:

    Возвращает 1, когда передано положительное целое число

    Возвращает -1, когда передано отрицательное целое число

    Возвращает 0 при прохождении 0. * /

    static int signum(int n)

    {

        if (n != 0)

        {

            return n > 0 ? 1 : -1;

        }

          

        else

        {

            return 0;

        

    }

      
}

Выход :

The maximum length of zig-zag sub-sequence in first sequence is: 3
The maximum length of zig-zag sub-sequence in second sequence is: 4

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

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

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

Самая длинная зигзагообразная подпоследовательность

0.00 (0%) 0 votes