Как стать автором
Моя лентаВсе потоки
Поиск
Написать публикацию
Обновить

Наибольшая общая возрастающая подпоследовательность

Время на прочтение10 мин
Количество просмотров1.2K
Алгоритмы * Занимательные задачкиПрограммирование *
Из песочницы

Предисловие

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

Условие задачи

Даны две последовательности, требуется найти и вывести их НОВП (наибольшую общую возрастающую подпоследовательность).

Формат ввода
Во входном файле записаны две последовательности. Каждая последовательность описывается двумя строками следующим образом: в первой строке идет длина последовательности N \ (1 \leq N \leq 500), во второй идут N целых чисел a_i (-2^{-31} \leq a_i \leq 2^{31} - 1) - члены последовательности.

Формат вывода
В первой строке выходного файла выведите длину наибольшей общей возрастающей подпоследовательности. Во второй строке выходного файла выведите саму подпоследовательность.

Решение

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

К сожалению, нельзя просто найти наибольшую общую подпоследовательность, а потом в ней найти наибольшую возрастающую.

Контрпример

Последовательности (1, 5, 3, 2, 1) и (5, 3, 2, 1, 5).
Наибольшей общей является подпоследовательность (5, 3, 2, 1), но длина наибольшей возрастающей в ней равна 1.
При этом существует возрастающая общая подпоследовательность (1, 5), длина которой равна 2.

Пусть на вход поданы последовательность first_array длины first_size и последовательность second_array длины second_size.
Рассмотрим следующую динамику: создадим двумерную таблицу dp размера first_size x second_size. Элемент на i-ой строке и j-ом столбце будет хранить длину НОВП для первых i символов последовательности first_array, и первых j символов последовательности second_array. При этом НОВП должна оканчиваться на a[i] (a[i] и b[j] должны быть равны). Если first_array[i] и second_array[j] различны, то будем хранить 0. Таблицу заполняем слева направо, сверху вниз.
Предположим, что в текущий момент необходимо найти значение элемента dp[i][j]. В случае, когда first_array[i] и second_array[j] совпадают, искомая НОВП будет оканчиваться на first_array[i], а вся остальная её часть будет являться НОВП для какой-либо другой пары индексов k и l (k < i, l < j). Тогда, нужно найти максимум из всех элементов dp[k][l] с подходящими k и l, после чего прибавить единицу - получим значение dp[i][j]. Не забываем проверять, что подпоследовательность действительно возрастающая (first_array[k] < first_array[i]).

Область поиска максимума при заполнении таблицы dp
Область поиска максимума при заполнении таблицы dp
Поиск длины НОВП
for (size_t i = 0; i < first_size; ++i) {
  for (size_t j = 0; j < second_size; ++j) {
    if (first_array[i] != second_array[j]) {
      // dp[i][j] уже 0, идем дальше
      continue;
    }
    dp[i][j] = 1;  // при равенстве элементов есть хотя бы одна НОВП длины 1

    // перебираем НОВП на подмассивах
    for (size_t k = 0; k < i; ++k) {
      for (size_t l = 0; l < j; ++l) {
        if (first_array[k] < first_array[i] && dp[k][l] + 1 > dp[i][j]) {
          dp[i][j] = dp[k][l] + 1;
          parents[i][j] = std::make_pair(k, l);
        }
      }
    }
  }
}

Для восстановления ответа создадим двумерный массив parents, который будет хранить пары из индексов, где первый элемент - индекс в первом массиве, второй - индекс во втором. parents[i][j] хранит (k, l), если dp[k][l] это максимум из всех доступных элементов таблицы dp при вычислении dp[i][j].

Весь код
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

std::vector<int> read_array() {
  size_t size = 0;
  std::cin >> size;
  std::vector<int> array(size, 0);
  for (size_t i = 0; i < size; ++i) {
    std::cin >> array[i];
  }
  return array;
}

std::vector<int> find_lcis(const std::vector<int>& first_array, const std::vector<int>& second_array) {
  size_t first_size = first_array.size();
  size_t second_size = second_array.size();
  std::vector<std::vector<int>> dp(first_size, std::vector<int>(second_size, 0));
  std::vector<std::vector<std::pair<size_t, size_t>>> parents(
    first_size,
    std::vector<std::pair<size_t, size_t>>(second_size, std::make_pair(0, 0))
  );

  // заполнение dp
  for (size_t i = 0; i < first_size; ++i) {
    for (size_t j = 0; j < second_size; ++j) {
      if (first_array[i] != second_array[j]) {
        // dp[i][j] уже 0, идем дальше
        continue;
      }
      dp[i][j] = 1;  // при равенстве элементов есть хотя бы одна НОВП длины 1

      // перебираем НОВП на подмассивах
      for (size_t k = 0; k < i; ++k) {
        for (size_t l = 0; l < j; ++l) {
          if (first_array[k] < first_array[i] && dp[k][l] + 1 > dp[i][j]) {
            dp[i][j] = dp[k][l] + 1;
            parents[i][j] = std::make_pair(k, l);
          }
        }
      }
    }
  }

  // восстановление ответа
  size_t best_first = 0;
  size_t best_second = 0;
  for (size_t i = 0; i < first_size; ++i) {
    for (size_t j = 0; j < second_size; ++j) {
      if (dp[i][j] > dp[best_first][best_second]) {
        best_first = i;
        best_second = j;
      }
    }
  }

  // теперь мы готовы восстановить ответ по матрице parents
  std::vector<int> answer(dp[best_first][best_second], 0);
  size_t current_first = best_first;
  size_t current_second = best_second;
  for (size_t i = 0; i < answer.size(); ++i) {
    answer[i] = first_array[current_first];

    // <-> x,y = parents[x][y].first, parents[x][y].second
    std::tie(current_first, current_second) = parents[current_first][current_second];
  }
  std::reverse(answer.begin(), answer.end());
  return answer;
}

int main() {
  std::vector<int> first_array = read_array();
  std::vector<int> second_array = read_array();

  std::vector<int> answer = find_lcis(first_array, second_array);
  std::cout << answer.size() << '\n';
  for (size_t i = 0; i < answer.size(); ++i) {
    std::cout << answer[i] << ' ';
  }
  std::cout << '\n';
}

Полученное решение имеет временную сложность O(N^2 \cdot M^2) (N - длина первого массива, M - длина второго).

Оптимизация 1.

Получили решение с большой временной сложностью. Как оптимизировать?
Сделаем условия для элементов dp более мягкими. Теперь dp[i][j] будет хранить длину НОВП для первых i символов последовательности first_array, и первых j символов последовательности second_array, но теперь first_array[i] не обязательно является концом НОВП (теперь элементы first_array[i] и second_array[j] могут быть различны).

Заполнять таблицу dp будем следующим образом:

  • Если i == 0, то при first_array[i] == second_array[j], очевидно, dp[i][j] = 1, иначе dp[i][j] = 0.

  • Если first_array[i] != second_array[j], то мы не можем добавить к какой-либо последовательности элемент first_array[i] в конец. Тогда в dp[i][j] положим максимальное значение из всех уже посчитанных с second_array[j] на конце. Т.е. максимум из dp[k][j], где k < i

  • Если first_array[i] == second_array[j], то найдём НОВП, в конец которой можно добавить second_array[j]. Для этого, аналогично первому решению, переберем все пары k и l (где k < i, l < j) и найдем максимум среди dp[k][l].

Заметим, что согласно алгоритму заполнения таблицы dp, элементы в ней не убывают при увеличении i (т.е. для любого значения j последовательность dp[0][j], dp[1][j], ..., dp[i - 1][j] нестрого возрастает).
Тогда, в случае неравенства first_array[i] и second_array[j] пропадает необходимость в переборе, т.к. мы сразу знаем что dp[i - 1][j] максимальный элемент и dp[i][j] = dp[i - 1][j].
В случае равенства можем заменим два цикла на один:

Оптимизация заполнения dp
// было
for (size_t i = 0; i < first_size; ++i) {
  for (size_t j = 0; j < second_size; ++j) {
    if (i == 0) {
      if (first_array[i] == second_array[j]) {
        dp[i][j] = 1;
      }
      continue;
    }
    if (first_array[i] != second_array[j]) {
      for (size_t k = 0; k < i; ++k) {
        if (dp[k][j] > dp[i][j]) {
          dp[i][j] = dp[k][j];
        }
      }
    } else {
      dp[i][j] = 1;
      for (size_t k = 0; k < i; ++k) {
        for (size_t l = 0; l < j; ++l) {
          if (dp[k][l] + 1 > dp[i][j] && second_array[l] < second_array[j]) {
            dp[i][j] = dp[k][l] + 1;
          }
        }
      }
    }
  }
}

// стало
for (size_t i = 0; i < first_size; ++i) {
  for (size_t j = 0; j < second_size; ++j) {
    if (i == 0) {
      if (first_array[i] == second_array[j]) {
        dp[i][j] = 1;
      }
      continue;
    }
    if (first_array[i] != second_array[j]) {
      dp[i][j] = dp[i - 1][j];
    } else {
      dp[i][j] = 1;
      for (size_t l = 0; l < j; ++l) {
        if (dp[i - 1][l] + 1 > dp[i][j] && second_array[l] < second_array[j]) {
          dp[i][j] = dp[i - 1][l] + 1;
        }
      }
    }
  }
}

Теперь, при заполнении родителей в случае first_array[i] != second_array[j] будем "ссылаться" на родителя лучшего варианта, т.е. dp[i - 1][j]:
parents[i][j] = parents[i - 1][j]
При first_array[i] == second_array[j] заполняем по-прежнему парой индексов с лучшей длиной НОВП.

Важно обратить внимание: теперь индексы из первого массива, которые хранятся в парах таблицы parents, не обязательно указывают на элементы искомой НОВП (мы ослабили условие). Следовательно, восстанавливать НОВП нужно через индексы второго массива.
Элементы dp растут при увеличении первого индекса, поэтому для поиска наибольшего элемента таблицы в конце достаточно пройтись по самому правому столбцу.

Весь код
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

std::vector<int> read_array() {
  size_t size = 0;
  std::cin >> size;
  std::vector<int> array(size, 0);
  for (size_t i = 0; i < size; ++i) {
    std::cin >> array[i];
  }
  return array;
}

std::vector<int> find_lcis(const std::vector<int>& first_array, const std::vector<int>& second_array) {
  size_t first_size = first_array.size();
  size_t second_size = second_array.size();
  std::vector<std::vector<int>> dp(first_size, std::vector<int>(second_size, 0));
  std::vector<std::vector<std::pair<size_t, size_t>>> parents(
    first_size,
    std::vector<std::pair<size_t, size_t>>(second_size, std::make_pair(0, 0))
  );

  // заполнение dp
  for (size_t i = 0; i < first_size; ++i) {
    for (size_t j = 0; j < second_size; ++j) {
      if (i == 0) {
        if (first_array[i] == second_array[j]) {
          dp[i][j] = 1;
        }
        continue;
      }
      if (first_array[i] != second_array[j]) {
        dp[i][j] = dp[i - 1][j];
        parents[i][j] = parents[i - 1][j];
      } else {
        dp[i][j] = 1;
        for (size_t l = 0; l < j; ++l) {
          if (dp[i - 1][l] + 1 > dp[i][j] && second_array[l] < second_array[j]) {
            dp[i][j] = dp[i - 1][l] + 1;
            parents[i][j] = std::make_pair(i - 1, l);
          }
        }
      }
    }
  }

  // восстановление ответа
  size_t best_first = first_size - 1;
  size_t best_second = 0;
  for (size_t j = 0; j < second_size; ++j) {
    if (dp[best_first][j] > dp[best_first][best_second]) {
      best_second = j;
    }
  }

  // теперь мы готовы восстановить ответ по матрице parents
  std::vector<int> answer(dp[best_first][best_second], 0);
  size_t current_first = best_first;
  size_t current_second = best_second;
  for (size_t i = 0; i < answer.size(); ++i) {
    answer[i] = second_array[current_second];

    // <-> x,y = parents[x][y].first, parents[x][y].second
    std::tie(current_first, current_second) = parents[current_first][current_second];
  }
  std::reverse(answer.begin(), answer.end());
  return answer;
}

int main() {
  std::vector<int> first_array = read_array();
  std::vector<int> second_array = read_array();

  std::vector<int> answer = find_lcis(first_array, second_array);
  std::cout << answer.size() << '\n';
  for (size_t i = 0; i < answer.size(); ++i) {
    std::cout << answer[i] << ' ';
  }
  std::cout << '\n';
}

Это решение имеет временную сложность O(N \cdot M^2).

Оптимизация 2.

Подробнее рассмотрим нахождение dp[i][j] при равенстве first_array[i] == second_array[j].
Мы заполняем таблицу слева направо, сверху вниз. Поэтому внутри каждой строки (i = const) можно считать элемент первого массива first_array[i] фиксированным. Именно с ним мы будем сравнивать элементы второго массива от second_array[0] до second_array[second_size - 1].

Рассмотрим заполнение каждой строки таблицы dp.

  • Перебираем по возрастанию индексы j второго массива

  • В случае неравенства first_array[i] != second_array[j] тратим O(1) времени, заполняя либо dp[i][j] = 1, либо dp[i][j] = dp[i - 1][j]

  • В случае равенства first_array[i] == second_array[j] пробегаем по всем индексам l от 0 до j - 1 и находим элемент второго массива, который меньше second_array[j], чтобы при этом величина dp[i - 1][l] была максимальна.

Получаем O(M^2) времени на каждую строку.

Т.к. first_array[i] в каждой строке постоянный, то получается, что при равенстве мы ищем максимум dp[i - 1][k], где k лежит от 0 до j - 1 и при это second_array[k] < first_array[i]. Попробуем оптимизировать O(M^2) до O(M):

Теперь мы будем хранить этот максимум в отдельной переменной. Будем использовать переменные best_len - само значение максимума и best_index - соответствующий максимуму индекс во втором массиве.
Тогда в процессе мы будем обновлять значения этих переменных, и в случае равенства first_array[i] == second_array[j] сможем быстро определить значение dp[i][j]:
dp[i][j] = best_len + 1

Обновлять значения этих переменных будем в случае, когда мы нашли элемент second_array[k] меньший first_array[i], при этом best_len < dp[k][i]. Тогда best_len = dp[k][i] и best_index = k.

Поиск длины НОВП
for (size_t i = 0; i < first_size; ++i) {
  size_t best_index = 0;
  int best_len = 0;
  for (size_t j = 0; j < second_size; ++j) {
    if (i == 0) {
      if (first_array[i] == second_array[j]) {
        dp[i][j] = 1;
      }
      continue;
    }
    if (first_array[i] != second_array[j]) {
      dp[i][j] = dp[i - 1][j];
      parents[i][j] = parents[i - 1][j];
      // проверяем можно ли обновить best_len
      if (first_array[i] > second_array[j] && dp[i - 1][j] > best_len) {
        best_len = dp[i - 1][j];
        best_index = j;
      }
    } else {
      if (best_len + 1 > dp[i][j]) {
        dp[i][j] = best_len + 1;
        parents[i][j] = std::make_pair(i - 1, best_index);
      }
    }
  }
}

Этим улучшением оптимизируем временную сложность алгоритма до O(N \cdot M).

Весь код
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

std::vector<int> read_array() {
  size_t size = 0;
  std::cin >> size;
  std::vector<int> array(size, 0);
  for (size_t i = 0; i < size; ++i) {
    std::cin >> array[i];
  }
  return array;
}

std::vector<int> find_lcis(const std::vector<int>& first_array, const std::vector<int>& second_array) {
  size_t first_size = first_array.size();
  size_t second_size = second_array.size();
  std::vector<std::vector<int>> dp(first_size, std::vector<int>(second_size, 0));
  std::vector<std::vector<std::pair<size_t, size_t>>> parents(
    first_size,
    std::vector<std::pair<size_t, size_t>>(second_size, std::make_pair(0, 0))
  );

  // заполнение dp
  for (size_t i = 0; i < first_size; ++i) {
    size_t best_index = 0;
    int best_len = 0;
    for (size_t j = 0; j < second_size; ++j) {
      if (i == 0) {
        if (first_array[i] == second_array[j]) {
          dp[i][j] = 1;
        }
        continue;
      }
      if (first_array[i] != second_array[j]) {
        dp[i][j] = dp[i - 1][j];
        parents[i][j] = parents[i - 1][j];
        // проверяем можно ли обновить best_len
        if (first_array[i] > second_array[j] && dp[i - 1][j] > best_len) {
          best_len = dp[i - 1][j];
          best_index = j;
        }
      } else {
        if (best_len + 1 > dp[i][j]) {
          dp[i][j] = best_len + 1;
          parents[i][j] = std::make_pair(i - 1, best_index);
        }
      }
    }
  }

  // восстановление ответа
  size_t best_first = first_size - 1;
  size_t best_second = 0;
  for (size_t j = 0; j < second_size; ++j) {
    if (dp[best_first][j] > dp[best_first][best_second]) {
      best_second = j;
    }
  }

  // теперь мы готовы восстановить ответ по матрице parents
  std::vector<int> answer(dp[best_first][best_second], 0);
  size_t current_first = best_first;
  size_t current_second = best_second;
  for (size_t i = 0; i < answer.size(); ++i) {
    answer[i] = second_array[current_second];

    // <-> x,y = parents[x][y].first, parents[x][y].second
    std::tie(current_first, current_second) = parents[current_first][current_second];
  }
  std::reverse(answer.begin(), answer.end());
  return answer;
}

int main() {
  std::vector<int> first_array = read_array();
  std::vector<int> second_array = read_array();

  std::vector<int> answer = find_lcis(first_array, second_array);
  std::cout << answer.size() << '\n';
  for (size_t i = 0; i < answer.size(); ++i) {
    std::cout << answer[i] << ' ';
  }
  std::cout << '\n';
}

Надеюсь, эта статья помогла вам лучше понять задачу и её решение. Желаю удачи в программировании!

Теги:
Хабы:
+5
Комментарии0
1
Карма
5
Рейтинг
@ConsigliereNumberTwo

Пользователь

Отправить сообщение

Публикации

Ближайшие события

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr