Как найти убывающая подпоследовательность

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

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

Например, рассмотрим следующую подпоследовательность:

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

 
Самая длинная убывающая подпоследовательность [12, 10, 9, 5, 3], длина которого равна 5; входная последовательность не имеет 6-членных убывающих подпоследовательностей.

 
Самая длинная убывающая подпоследовательность в этом примере не уникальна: например, [12, 10, 6, 5, 3] — еще одна убывающая подпоследовательность той же длины в той же входной последовательности.

Потренируйтесь в этой проблеме

Мы можем использовать рекурсия Для решения этой проблемы. Для каждого элемента есть две возможности:

Наконец, верните максимальное значение, которое мы получим, включив или исключив текущий элемент. Базовым случаем рекурсии будет отсутствие элементов. Ниже приведена реализация этой идеи на C++, Java и Python:

Временная сложность приведенного выше решения экспоненциальна и занимает место в стеке вызовов.
 

 
Проблема имеет оптимальное основание. Это означает, что проблема может быть разбита на более мелкие, простые “подзадачи”, которые затем могут быть разделены на еще более простые, более мелкие подзадачи, пока решение не станет тривиальным. Приведенное выше решение также демонстрирует перекрывающиеся подзадачи. Если мы нарисуем дерево рекурсии решения, мы увидим, что одни и те же подзадачи вычисляются повторно.

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

 
Мы также можем решить эту проблему восходящим способом. При подходе «снизу вверх» мы сначала решаем меньшие подзадачи, а затем на их основе решаем более крупные подзадачи. Следующий восходящий подход вычисляет L[i], для каждого 0 <= i < n, в котором хранится длина самой длинной убывающей подпоследовательности подмассива nums[0…i] что заканчивается nums[i]. Вычислять L[i], рассмотрим LDS всех меньших значений i (сказать j) уже вычислено и выбрать максимальное L[j], куда nums[j] больше, чем текущий элемент nums[i]. У него такое же асимптотическое время выполнения, как и у Memoization, но нет накладных расходов на рекурсию.

Ниже приведена реализация этой идеи на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n²) и требует O(n) дополнительное пространство, где n — размер заданной последовательности.

Как распечатать ЛДС?

Рассмотренные выше методы печатают только длину LDS, но не печатают саму LDS. Чтобы распечатать LDS, мы должны сохранить самую длинную убывающую подпоследовательность в таблице поиска, а не хранить только длину LDS.

 
Например, рассмотрим следующий массив:

nums[] = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Самая длинная убывающая подпоследовательность LDS[i] подмассива nums[0…i] что заканчивается nums[i] находятся:

LDS[0] — 0
LDS[1] — 8
LDS[2] — 8 4
LDS[3] — 12
LDS[4] — 8 4 2
LDS[5] — 12 10
LDS[6] — 12 10 6
LDS[7] — 14
LDS[8] — 8 4 2 1
LDS[9] — 12 10 9
LDS[10] — 12 10 6 5
LDS[11] — 14 13
LDS[12] — 12 10 6 5 3
LDS[13] — 14 13 11
LDS[14] — 12 10 9 7
LDS[15] — 15

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n²) и требует O(n²) дополнительное пространство, где n — размер заданной последовательности.

Given an array of N integers, find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in strictly decreasing order. 
Examples:  

Input: arr[] = [15, 27, 14, 38, 63, 55, 46, 65, 85] 
Output: 3 
Explanation: The longest decreasing subsequence is {63, 55, 46} 
Input: arr[] = {50, 3, 10, 7, 40, 80} 
Output: 3 
Explanation: The longest decreasing subsequence is {50, 10, 7} 

The problem can be solved using Dynamic Programming
Optimal Substructure: 
Let arr[0…n-1] be the input array and lds[i] be the length of the LDS ending at index i such that arr[i] is the last element of the LDS. 
Then, lds[i] can be recursively written as: 

lds[i] = 1 + max(lds[j]) where i > j > 0 and arr[j] > arr[i] or 
lds[i] = 1, if no such j exists.

To find the LDS for a given array, we need to return max(lds[i]) where n > i > 0.  

Length of LDS is 3

Time Complexity: O(n²) 
Auxiliary Space: O(n)
Related Article: https://www.geeksforgeeks.org/longest-increasing-subsequence/

Longest Decreasing Subsequence in O(n*log(n)) :

Another approach to finding the Longest Decreasing Subsequence is using the Longest Increasing Subsequence approach in n*log(n) complexity. Here is the link to find the details of the approach with O(n*log(n)) complexity https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/.

We can observe that the length of the Longest Decreasing Subsequence of any array is same as the length of the Longest Increasing Subsequence of that array if we multiply all elements by -1.

For example:

arr[] = [15, 27, 14, 38, 63, 55, 46, 65, 85] 
then the length of longest decreasing subsequence of this array is same as length of longest increasing subsequence of arr[]=[-15, -27, -14, -38, -63, -55, -46, -65, -85]

In both cases the length is 3.

Steps to solve this problem:

1. Check if array is zero than return zero.

2. Declare a vector tail of array size.

3. Declare a variable length=1.

4. Initialize tail[0]=v[0].

5. Iterate through i=1 till size of array:

    *Initialize auto b=tail.begin and e=tail.begin+length.

    *Initialize auto it to lower bound of v[i].

    *Check if it is equal to tail.begin+length than tail[length++]=v[i].

    *Else update value at it =v[i].

6. Return length.

Below is the code of the above approach.

Length of Longest Decreasing Subsequence is 3

Time Complexity: O(n*logn)
Auxiliary Space: O(n)

Last Updated :
28 Feb, 2023

Like Article

Save Article

1. Название Описание

[Вопрос 1] Найти самый длинный из массивапрерывистыйНисходящая подпоследовательность

[Вопрос 2] Найти самый длинный из массиванепрерывныйНисходящая подпоследовательность

Во-вторых, идеи решения проблем

[Вопрос 1] Используя идею динамического программирования, пусть dp [i] будет длиной убывающей подпоследовательности с i в качестве конечного элемента, тогда формула рекурсии:
dp[i] = max(dp[j]+1,dp[i]) (j<i && array[j]>array[i])

[Вопрос 2] Используйте два курсора начала и конца, чтобы записать начало и конец последовательно убывающих подпоследовательностей, и обновите значения начала и конца, как только они столкнутся с приращениями. Используйте max_len для записи длины самой длинной непрерывно убывающей подпоследовательности

В-третьих, алгоритм решения проблем

[Вопрос 1] Самый длинныйпрерывистыйУменьшающаяся подпоследовательность — динамическое программирование

/**************************************
author:tmw
date:2018-10-21
**************************************/
#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (a>b?a:b)

/**
* @param int * заголовок массива в массив
 * @param int array_len длина массива
**/
int findMaxUncontinuesSubArray(int* array, int len)
{
    int* dp = (int*)malloc(len*sizeof(int));
    int i,j;
    for(i=0; i<len; i++)
    {
                 dp [i] = 1; // инициализация массива dp
        for(j=0; j<i; j++)
        {
            if(array[j]>array[i])
                                 dp [i] = max (dp [j] +1, dp [i]); // Включить массив [j] в последовательность с i в качестве конечного элемента
        }
    }
         // Находим самую длинную прерывистую убывающую подпоследовательность с i как конечный элемент
    int max_len = dp[0];
    for(i=1; i<len; i++)
    {
        if(max_len<dp[i])
            max_len = dp[i];
    }
    return max_len;
}

[Вопрос 2] Самый длинныйнепрерывныйУбывающая подпоследовательность

/**************************************
author:tmw
date:2018-10-21
**************************************/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) (a>b?a:b)
int findMaxContinueSubArray(int* array, int len)
{
    if(array==NULL || len<0) return -1;

    int start = 0;
    int end = 1;
    int max_len = INT_MIN;
    while(start<end && end<len)
    {
        while(array[end-1]>array[end] && end<len)
        {
            if(max_len<end-start+1)
            {
                printf("[%d-%d]n",start,end);
                max_len = end-start+1;
                printf("%dn",max_len);
            }
            end++;
        }
        if(array[end-1]<array[end])
        {
            start = end;
            end++;
        }
    }
    return max_len;
}

Мечты все еще нужны, если они сбываются ~~~ ヾ (◍ ° ∇ ° ◍) ﾉ ﾞ ~~~~~~~~~~~~

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

Очевидно, что строго монотонная последовательность является монотонной.

Теорема о связи длины НВП и НУП

Следствие из теоремы

См. также

• Задача о минимуме/максимуме скалярного произведения
• Теорема Кэли
• Матричное представление перестановок

Источники информации

• Википедия — Последовательность

• Wikipedia — Longest increasing subsequence

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

Подпоследовательность
последовательности (x_n) —
это последовательность
,
где (k_n) — возрастающая
последовательность элементов множества
натуральных чисел.

Иными словами, подпоследовательность
получается из последовательности
удалением конечного или счётного числа
элементов.

Примеры

• Последовательность простых
  чисел является подпоследовательностью
  последовательности натуральных чисел.

• Последовательность натуральных чисел,
  кратных 12,
  является подпоследовательностью
  последовательности чётных
  натуральных чисел.

Свойства

• Всякая последовательность является
  своей подпоследовательностью.

• Для всякой подпоследовательности
  верно,
  что
  .

• Подпоследовательность сходящейся
  последовательности сходится к тому же
  пределу, что и исходная последовательность.

• Если все подпоследовательности некоторой
  исходной последовательности сходятся,
  то их пределы равны.

• Любая подпоследовательность бесконечно
  большой последовательности также
  является бесконечно большой.

• Из любой неограниченной числовой
  последовательности можно выделить
  бесконечно большую подпоследовательность,
  все элементы которой имеют определённый
  знак.

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

Предельная точка последовательности

Основная статья: Предельная
точка

Предельная точка последовательности
— это точка, в любой окрестности которой
содержится бесконечно много элементов
этой последовательности. Для сходящихся
числовых последовательностей предельная
точка совпадает с пределом.

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

Основная статья: Предел
последовательности

Предел последовательности —
это объект, к которому члены
последовательности приближаются с
ростом номера. Так в произвольном
топологическом
пространстве пределом последовательности
называется элемент, в любой окрестности
которого лежат все члены последовательности,
начиная с некоторого. В частности для
числовых последовательностей предел
— это число, в любой окрестности которого
лежат все члены последовательности
начиная с некоторого.

Частичный
предел последовательности — это
предел одной из её подпоследовательностей.
У сходящихся числовых последовательностей
он всегда совпадает с обычным пределом.

Верхний предел последовательности
— это наибольшая предельная точка этой
последовательности.

Нижний предел последовательности
— это наименьшая предельная точка этой
последовательности.

Некоторые виды последовательностей

• Стационарная последовательность
  — это последовательность, все члены
  которой, начиная с некоторого, равны.

(x_n) стационарная

Ограниченные и неограниченные последовательности

В предположении о линейной
упорядоченности множества X
элементов последовательности можно
ввести понятия ограниченных и
неограниченных последовательностей.

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

(x_n) ограниченная сверху

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

(x_n) ограниченная снизу

• Ограниченная последовательность
  (ограниченная с обеих сторон
  последовательность) — это
  последовательность, ограниченная и
  сверху, и снизу.

(x_n) ограниченная

• Неограниченная последовательность —
  это последовательность, которая не
  является ограниченной.

(x_n) неограниченная

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #