Задача. С клавиатуры вводится набор N целых чисел. Найти наибольшую длину возрастающей подпоследовательности.
Пример
N = 10
10 11 20 3 9 27 100 10 5 4
Наибольшая длина: 4
В этом ряду возрастающих подпоследовательностей две: числа 10 11 20 и 3 9 27 100. Наибольшая длина - 4, четыре числа в подпоследовательности 3 9 27 100.
Как будем решать задачу
Введем N - количество чисел в наборе.
Введем с клавиатуры первое число a и за длину возрастающей подпоследовательности возьмем k = 1. За искомую максимальную длину возьмем m = 1.
Далее в цикле для t от 2 до N:
- введем число b
- выполним проверку b>a, если условие истинно, то значение k увеличим на 1 (считаем длину возрастающей подпоследовательности), иначе значением k возьмем за 1 (возрастающая подпоследовательность оборвалась)
- найдем максимальную длину m
- значение переменной a перезапишем на значение b
Таблица выполнения алгоритма
|
a |
b |
b > a |
k |
k > m |
m |
|
10 |
|
|
1 |
|
1 |
|
11 |
11 |
11 > 10 да |
2 |
2 > 1 да |
2 |
|
20 |
20 |
20 > 11 да |
3 |
3 > 2 да |
3 |
|
3 |
3 |
3 > 20 нет |
1 |
1 > 3 нет |
|
|
9 |
9 |
9 > 3 да |
2 |
2 > 3 нет |
|
|
27 |
27 |
27 > 9 да |
3 |
3 > 3 нет |
|
|
100 |
100 |
100 > 27 да |
4 |
4 > 3 да |
4 |
|
10 |
10 |
10 > 100 нет |
1 |
1 > 4 нет |
|
|
5 |
5 |
5 > 10 нет |
1 |
1 > 4 нет |
|
|
4 |
4 |
4 > 5 нет |
1 |
1 > 4 нет |
|
|
|
|
|
|
|
Вывод 4 |
Программа решения задачи на языке Паскаль
var a,b,k,m,t,N:integer;
begin
readln(N);
read(a); k:=1; m:=1;
for t:=2 to N do
begin
read(b);
if b>a then k+=1 else k:=1;
m:=max(k,m); //функция нахождения максимума из двух значений
a:=b;
end;
writeln('наибольшая длина возрастающей подпоследовательноси: ',m);
end.
Результат запуска программы
Комментариев нет:
Отправить комментарий