Задание:
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит сумму наибольшей по длине возрастающей последовательности подряд идущих элементов. Если таких последовательностей несколько, можно вывести любую из них. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
Паскаль |
|
Си |
|
Естественный язык |
Объявляем массив A из 30 элементов. Объявляем целочисленные переменные i, l, lmax, s, smax. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. ... |
Решение:
Обратим внимание, что нужно найти не длину, а сумму наибольшей (то есть, самой длинной!) возрастающей последовательности (то есть, такой, в которой каждый следующий элемент строго больше предыдущего). В переменных l и s будем хранить длину и сумму текущей (рассматриваемой сейчас) последовательности, а в переменных lmax и smax – значения для наибольшей последовательности.
Решение на естественном языке. Записываем в переменную lmax начальное значение 0, в переменную l – значение 1, а в переменную smax – значение первого элемента массива. В цикле рассматриваем все элементы массива, начиная со 2-ого до 30-ого. Если очередной элемент больше предыдущего, увеличиваем переменную l на 1, а к переменной s добавляем значение этого элемента; иначе записываем 1 в переменную l и значение этого элемента в s. После этого (в теле цикла) сравниваем l и lmax; если l > lmax (нашли новую самую длинную возрастающую цепочку), записываем значение s в smax.
Решение на Паскале.
const N=30;
var a: array [1..N] of integer;
i, l, lmax, s, smax: integer;
begin
for i:=1 to N do readln(a[i]);
lmax:=0; l:=1; s:=a[1];
for i:=2 to N do begin
if a[i] > a[i-1] then begin
l:=l+1; s:=s+a[i]
end
else begin
l:=1; s:=a[i]
end;
if l > lmax then begin
lmax:=l;
smax:=s
end
end;
writeln(smax)
end.