Левый Аккаунт
Ученик
(2)
1 неделю назад
#include <iostream>
#include <vector>
#include <algorithm>
// Функция для нахождения наибольшей возрастающей подпоследовательности
std::vector<int> longestIncreasingSubsequence(const std::vector<int>& sequence) {
int n = sequence.size();
std::vector<int> dp(n, 1); // dp[i] - длина наибольшей возрастающей подпоследовательности, заканчивающейся на i
std::vector<int> prev(n, -1); // prev[i] - индекс предыдущего элемента в подпоследовательности
int maxLength = 0; // Длина наибольшей подпоследовательности
int maxIndex = 0; // Конечный индекс наибольшей подпоследовательности
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (sequence[j] < sequence[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
maxIndex = i;
}
}
// Восстановление наибольшей возрастающей подпоследовательности
std::vector<int> lis;
for (int i = maxIndex; i != -1; i = prev[i]) {
lis.push_back(sequence[i]);
}
std::reverse(lis.begin(), lis.end());
return lis;
}
int main() {
int n;
std::cout << "Введите количество элементов в последовательности: ";
std::cin >> n;
std::vector<int> sequence(n);
std::cout << "Введите последовательность: ";
for (int i = 0; i < n; ++i) {
std::cin >> sequence[i];
}
std::vector<int> lis = longestIncreasingSubsequence(sequence);
std::cout << lis.size() << std::endl;
for (int num : lis) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Входные данные
6
3 29 5 5 28 6
Результат работы
3
3 5 28