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


Сложный уровень Легко
Часто спрашивают в Амазонка Avalara Набор фактов Фуркиты Microsoft
массив Динамическое программирование ЛИС

Задача «Самая длинная подпоследовательность, при которой разница между смежными объектами равна единице» утверждает, что вам дается целое массив. Теперь вам нужно найти длину самой длинной подпоследовательности, при которой разность соседних элементов равна 1.

Пример

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

1 2 3 4 7 5 9 4
6

объяснение

Как мы видим, есть две подпоследовательности, которые следуют условию. Это {1, 2, 3, 4, 5, 4}, а второй - {7, 8}. Итак, самая длинная подпоследовательность - первая. Таким образом, ответ - 6.

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

Наивным подходом было бы создание таких возможных подпоследовательностей. Но мы знаем, что создание подпоследовательностей - очень трудоемкая задача. Поскольку это потребует рекурсии и имеет экспоненциальную временную сложность. Итак, чтобы решить проблему, нам нужен лучший подход. Лучшим подходом было бы динамическое программирование. Потому что проблема аналогична проблеме самой длинной возрастающей подпоследовательности. В этой задаче нам нужно найти самую длинную подпоследовательность, соседние элементы которой должны иметь разность, равную 1. Итак, чтобы решить задачу, мы начинаем обход элементов входного массива.

Перед обходом мы устанавливаем базовый вариант, который является нашим первым элементом. Мы всегда можем создать подпоследовательность длины 1. Если мы выберем один элемент. Теперь, продвигаясь вперед, мы продолжим проверять в обратном направлении, что если мы каким-то образом найдем элемент, который имеет абсолютную разницу в 1 с текущим элементом. Затем мы можем просто добавить текущий элемент к подпоследовательности, в которой другой элемент был последним. И когда мы находим такой элемент, мы продолжаем обновлять максимальную длину нашей подпоследовательности, заканчивающейся на текущем элементе. И после вычисления всех этих значений мы находим максимум из всех этих значений. Это ответ на нашу проблему.

Код:

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

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

Код Java для самой длинной подпоследовательности, такой, что разница между смежными объектами равна одному

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

Анализ сложности

Сложность времени

О (N ^ 2), потому что у нас было две петли. Один просто проходил по всем элементам, а другой проходил по всем элементам, которые были пройдены. Таким образом, временная сложность алгоритма становится полиномиальной.

Космическая сложность

НА), поскольку нам нужно было сохранить результат для всех элементов, которые мы прошли до сих пор. Таким образом, сложность пространства линейна.