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

Чтобы помочь Сергею найти подпоследовательность, в которой мощности ступеней ракеты строго возрастают, мы можем использовать алгоритм, который находит наиболее длинную возрастающую подпоследовательность (LIS).

Вот простой способ реализации этого на Python:

def longest_increasing_subsequence(sequence):
    if not sequence:
        return []

    # Массив для хранения длины наибольшей возрастающей подпоследовательности
    lis_lengths = [1] * len(sequence)
    prev_index = [-1] * len(sequence)

    # Заполнение массива lis_lengths
    for i in range(1, len(sequence)):
        for j in range(i):
            if sequence[i] > sequence[j]:  # Если мощность i-й ступени больше j-й
                if lis_lengths[i] < lis_lengths[j] + 1:
                    lis_lengths[i] = lis_lengths[j] + 1
                    prev_index[i] = j

    # Находим максимальную длину LIS
    max_length = max(lis_lengths)
    max_index = lis_lengths.index(max_length)

    # Восстанавливаем саму подпоследовательность
    lis_sequence = []
    while max_index != -1:
        lis_sequence.append(sequence[max_index])
        max_index = prev_index[max_index]

    # Возвращаем последовательность в правильном порядке
    lis_sequence.reverse()
    return lis_sequence

# Исходные мощности ступеней ракеты
power_levels = [2, 5, 3, 53, 4, 7, 3, 8, 4, 9, 6, 7]
result = longest_increasing_subsequence(power_levels)

# Преобразуем последовательность в строку и выводим
print(" ".join(map(str, result)))

Этот код выполняет следующие шаги:

1. Создает массив lis_lengths, который хранит длину наибольшей возрастающей подпоследовательности для каждого элемента.
2. Заполняет этот массив, сравнивая текущий элемент с предыдущими и обновляя длину последовательности.
3. Находит максимальную длину и восстанавливает саму возрастающую подпоследовательность, используя массив prev_index.
4. Наконец, выводит результат.

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