Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

ПОМОГИТЕ ПРОШУ С С++

Leyla Nuriyeva Ученик (193), открыт 1 неделю назад
Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.
Входные данные

6
3 29 5 5 28 6
Результат работы

3
3 5 28
2 ответа
Левый Аккаунт Ученик (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;
}
Leyla NuriyevaУченик (193) 1 неделю назад
СПАСИБО
А можете другую задачу тоже пж решить
Похожие вопросы