Другие языки программирования и технологии

Найти наибольшую возрастающую последовательность в массиве С++

Допустим, дан массив чисел {4,6,7,4,7,8,9}
Нужно чтобы программа выводила 4,7,8,9. Не прошу писать коды, просто объясните алгоритм. Благодарю
Юрий Гагарин
Юрий Гагарин
75
Объявляем числа TEMP_ MAX, T_IND, IND и МАХ=0
Два цикла
Первый просто перебирает массив от i=0 до конца
{
TEMP_MAX = 0

Второй перебирает от k=i до конца.
{
В нем проверяется - является ли элемент k больше k+1. Если да, то
TEMP_MAX = TEMP_MAX + 1
T_IND = k
}
Если TEMP_MAX > MAX, то
MAX = TEMP_MAX и
IND = T_IND
}
Выводим массив начиная с i=IND либо до конца, либо до элемента, который будет меньше текущего i

Пля, наверное было бы проще написать фрагмент кода? Но ты же просил с объяснениями
Шуи Санга
Шуи Санга
63 126
Лучший ответ
Введи переменную, равную нулю.
Найди минимум, больший этой переменной. Выведи значение и присвой его переменной.
Повторяй пункт 2, пока не переберёшь все значения.
АЛ
Александр Лозовицкий
56 893
А почему не 4 6 7 8 9 ?
Дархан Бегалин
Дархан Бегалин
71 962
..:: K[N]G ::.. тогда уже 4 6 7 8 9
Начинаем с первого элемента массива и идём до конца. Если весь массив состоит только из возрастающих элементов, то он весь и будет максимально возрастающей последовательностью. Если же нет - тогда запоминаем длину цепочки и первый "пóртящий" возрастание элемент. С этого "пóртящего" элемента начинаем новый цикл проверки на возрастание до конца массива или до нового "пóртящего" элемента. И так далее в цикле по условию. Может оказаться, что наидлиннейшая возрастающая последовательность не единственная, тогда надо запоминать все растущие последовательности одинаковой максимальной длины. Может оказаться, что максимальная длина последовательности равна единице - такое произойдёт, если все элементы массива не возрастают. Тогда возрастающих последовательностей вообще нет - единичные элементы нельзя ведь считать за таковые!..
[*pro100_ Dumbass*]
[*pro100_ Dumbass*]
28 648
Павло Григорьев В этом решении учитываются только непрерывные последовательности. В условии о непрерывности ничего не сказано. В общем случае последовательность может быть разрывной: 4,6,7,8,9 для примера автора (а не 4,7,8,9 - как будет по вашему алгоритму). То есть алгоритм должен быть сложнее.
Выводим первое число, присваиваем переменной, берем следующее и, если оно больше переменной, переменной присваиваем его и выводим, если нет - переходим к следующему - весь алгоритм.
Слава Ярков
Слава Ярков
5 984
Дархан Бегалин и что этот алгоритм выдаст на тестовых данных
100,1,2,3,4,5,6,7,8,9
?
Слава Ярков Не сразу понял условие, поэтому алгоритм не решает задачу. Его нужно пустить циклом по всем элементам массива, проверяя, выбран ли уже начальный элемент в какую-либо последовательность. Если выбран, то переходить к следующему (т. к. выбираемая последовательность будет частью уже выбранной), если нет - выбирать последовательность, начиная с этого элемента. Цикл обрывать, когда число оставшихся элементов массива будет меньше числа элементов в наибольшей выбранной последовательности. Вариант с рекурсивной функцией, описанный Sergey, наверное правилен (не проверял), но без рекурсии будет, по-моему, быстрее.
Рекурсия. Пишите функцию которая выбирает или нет очередное число. Время пропорционально 2^N.
Суть: запускаете функцию на первое число два раза. Сначала с параметром выбрать это число, потом с параметром не выбирать. Данная функция вызывает себя но уже для следующего числа также два раза. И так до тех пор пока не будут выбраны все числа, пока выбранное число соответствует критерию отбора (больше предыдущего) или длина текущей последовательности гарантированно меньше уже найденной. Данная функция может заполнять некоторый глобальный массив выбранными значениями. Чтоб удобно было смотреть текущий результат.
Как то так.
РЛ
Руслан Лавриков
2 681
Слава Ярков По-моему, без рекурсии проще. Например так: чуть изменю пример автора для наглядности. Возьмем массив {5,7,4,6,7,4,7,8,9,3,1}. Во-первых, его можно сразу урезать, откинув два последних числа (и вообще любую убывающую последовательность в конце, кроме первого члена 9,3,1 - откидываем хвост кроме 9. Это стоит сделать для сокращения циклических операций. Во-вторых определяем дополнительный логический массив {.F.,.F.,.F.,.F.,.F.,.F.,.F.,.F.,.F.} - длиной в укороченный основной. Запускаем цикл по элементам основного (урезаного) массива. Ищем возрастающую последовательность начиная с первого элемента, попутно меняя во втором массиве для соответствующих выбранным элементам с .F. на .Т.. То есть на первом шаге будет выбрана последовательность 5,7,8,9, а второй массив будет иметь вид: (см. далее)

Похожие вопросы