Условие

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Напомним:

Последовательность xx называется подпоследовательностью последовательности y, если x получается из *y* удалением нескольких (возможно, нуля или всех) элементов.

Наибольшая общая подпоследовательность - последовательность наибольшей длины, которая является подпоследовательностью обеих последовательностей.

Примеры

Ввод: 3 1 2 3 3 2 3 1 Вывод: 2 3

Ввод: 3 1 2 3 3 3 2 1 Вывод: 1

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Чтение первой последовательности
    val n = reader.readLine().toIntOrNull() ?: 0
    val seq1 = if (n > 0) reader.readLine().split(" ").mapNotNull { it.toIntOrNull() } else emptyList()

    // Чтение второй последовательности
    val m = reader.readLine().toIntOrNull() ?: 0
    val seq2 = if (m > 0) reader.readLine().split(" ").mapNotNull { it.toIntOrNull() } else emptyList()

    // Создаем таблицу для динамического программирования
    val dp = Array(n + 1) { IntArray(m + 1) }

    // Заполняем таблицу
    for (i in 1..n) {
        for (j in 1..m) {
            if (seq1[i - 1] == seq2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    // Восстановление ответа
    val result = mutableListOf<Int>()
    var i = n
    var j = m
    while (i > 0 && j > 0) {
        when {
            seq1[i - 1] == seq2[j - 1] -> {
                result.add(seq1[i - 1])
                i--
                j--
            }
            dp[i - 1][j] > dp[i][j - 1] -> i--
            else -> j--
        }
    }

    // Вывод результата в обратном порядке
    writer.write(result.reversed().joinToString(" ") + "\\n")

    reader.close()
    writer.close()
}