Сама задача звучит так: Найти максимально длинную возрастающую последовательность. Элементы не обязательно должны идти последовательно. E.g.: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} --> {2, 4, 6, 8} Сам сидел думал дня 3 и ничего дельного в голову не идёт подскажите как делать такое может подход какой есть чтобы подступиться к задаче, а я ни сном ни духом.
2 ответа
Ну есть решение на c++ вот
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int mas[1000];
for(int i = 0; i < n; i++)
cin >> mas[i];
int count[1000];
count[0] = 1;
for(int i = 1; i < n; i++){
count[i] = 1;
for(int j = 0; j < i; j++){
if(mas[i] > mas[j] && count[j] + 1 > count[i])
count[i] ++;
}
}
sort(count, count + n);
cout << count[n - 1];
return 0;
}
- Создаём массив для длин подпоследовательностей и заполняем его 1.
- Пробегаемся по массиву с последовательностью со второго элемента и ищем элемент меньше него с максимальным значением во втором массиве, прибавляем к этому значению 1 и записываем во второй массив. 3)Выводим максимальное значение из второго массива.
-
да у меня проблема такая что я сам хочу сделать, а не выходит,думал может есть какой подход к задаче– Mark13 сен 2020 в 16:31
-
Я думал может делать типа идём циклом for и внутри ещё while и типа когда встречаем что от текущего появился элемент больший начинаем типа отсчитывать и следить за последовательностью, но там проблема что она может разрываться и тогда не работает– Mark13 сен 2020 в 16:34
-
-
-
2@Vlad261280 Какая разница что алгоритм работает, если в тегах стоит другой язык? Представь, что тебе на вопрос по плюсах ответили кодом на питоне или брейнфаке аргументировав тем что код работает. Тебе от этого легче станет?) 13 сен 2020 в 17:46
Первым алгоритмом мы заполняем массив mas[], потом создаем массив arr[] первый элемент которого равен единице, а остальные равны нулю. Потом опять идет цикл for(int i)который начинается с 1 и до конца, в нем есть еще один цикл for(int j) который идет с самого начала и до i. В нем мы проверяем если i-элемент, больше j-элемента, то во второй массив на j позицию добавляем единицу. Во время цикла запоминаем лучший результат и выводим его.
-
поподробнее можете расписать идею,а то я что-то сижу и не понимаю как оно работает, вижлы нет чтобы код протестить– Mark13 сен 2020 в 16:48
-
3
-