Самая длинная подпоследовательность из массива пар, в которых первый элемент увеличивается, а второй элемент уменьшается.

Учитывая массив пар A[][] размера N , задача состоит в том, чтобы найти самые длинные подпоследовательности, в которых первый элемент увеличивается, а второй элемент уменьшается.

Примеры:

Input: A[]={{1, 2}, {2, 2}, {3, 1}}, N = 3
Output: 2
Explanation: The longest subsequence satisfying the conditions is of length 2 and consists of {1, 2} and {3, 1};

Input: A[] = {{1, 3}, {2, 5}, {3, 2}, {5, 2}, {4, 1}}, N = 5
Output: 3

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

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

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

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

Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте массив dp[] , где dp[i] хранит длину самой длинной подпоследовательности, которая может быть сформирована из элементов до индекса i .
• Перебрать диапазон [0, N-1] , используя переменную i :
  • Базовый вариант: Обновите dp[i] как 1.
  • Перебрать диапазон [0, i – 1] , используя переменную j :
    • Если A[j].first меньше, чем A[i].first, а A[j].second больше, чем A[i].second, то обновите dp[i] как максимум dp[i] и dp[j ] + 1.
  • Наконец, напечатайте dp[N-1] .

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

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)