Определить самое большое количество подряд идущих максимумов массива

Задача

Дан массив, например, состоящий только из 0 и 1. Определить самое большое количество подряд идущих единиц и вывести на экран индексы начала и конца этого диапазона.

Решение

Алгоритм решения задачи: 

  • Если очередной элемент массива равен 1 (максимуму), то увеличить "текущий" счетчик максимумов.
  • Иначе (встретили 0) сравнить значение текущего счетчика максимумов со значением, записанном в переменной для хранения наибольшего числа подряд идущих максимумов (max_count). Если значение счетчика больше, то перезаписать значение переменной max_count и запомнить индекс первого или последнего элемента в найденной последовательности.

Программа на языке Паскаль:

const
	n = 50;
var
	arr: array[1..n] of byte;
	i,count,max_count,max_id: byte;
begin
	randomize;
	for i:=1 to n do begin // заполнение и вывод массива
		arr[i] := random(2); // диапазон [0;1]
		write(arr[i]:2);
		if i mod 10 = 0 then writeln; // переход после каждого 10-го на новую строку
	end;
 
	count := 0; // счетчик текущего количества максимумов
	max_count := 0; // запоминание самого большого количества максимумов
	max_id := 0; // индекс первого элемента в самой длинной последовательности максимумов
	for i:=1 to n do begin
		if arr[i] = 1 then
			count := count + 1
		else begin
			if count > max_count then begin
				max_count := count;
				max_id := i - count;
			end;
			count := 0
		end;			
	end;
	writeln('[',max_id,';',max_id+max_count-1,']');
end.

Пример выполнения кода:

 1 0 0 0 1 1 0 1 1 1
 0 1 0 0 0 1 0 0 1 1
 1 1 0 1 1 1 0 0 0 0
 1 0 1 1 1 1 1 0 1 0
 0 1 1 1 1 1 0 0 0 0
[33;37]

Код работает не для всех случаев. Попробуйте его использовать, если вместо последних 4-х нулей в Вашем примере будут единицы... А если весь массив будет из единиц? ;-)

Не обработан случай, когда массив заканчивается не нулем. Надо после цикла сделать дополнительную проверку.

Тема

Одномерные массивы

Уровень

Комбинированные задачи

Теги

Добавить комментарий