Оптимизация, алгоритм не проходит по времени

@iama · Регистрация: 30.07.2010

Студворк — интернет-сервис помощи студентам

Задание

Последовательность a1, a2, a3, … , an-1, an называется пилообразной, если она удовлетворяет одному из следующих условий:
1) a1 < a2 > a3 < … > an-1 < an
2) a1 > a2 < a3 > … < an-1 > an

Дана числовая последовательность. Требуется определить длину самой длинной ее пилообразной непрерывной подпоследовательности.
Входные данные

В первой строке входного файла INPUT.TXT записано натуральное число N – количество элементов последовательности. Во второй строке файла через пробел записаны N элементов целочисленной последовательности {ai}. Ограничения: N<10^6, |ai| < 32000.
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — длину самой длиной непрерывной пилообразной подпоследовательности.

Реализация

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var n, i, j, k, a, b: integer;
r, get_out: array [1..1000000] of boolean;
inf, outf: text;
label ex, next;
begin
assign(inf, 'INPUT.TXT'); reset(inf);
assign(outf, 'OUTPUT.TXT'); rewrite(outf);
 
 
readln(inf, n); read(inf, a);
for i := 1 to n do get_out[i] := false;
for i := 2 to n do begin
  b := a;
  read(inf, a);
  if a > b then r[i-1] := false
  else if a < b then r[i-1] := true
  else if a = b then get_out[i-1] := true;
 
end;
 
for i := n downto 2 do
  for j := 1 to n - i + 1 do begin
 
    for k := j to j + i - 3 do
      if (get_out[k]) or not (r[k] xor r[k + 1]) then goto next;
 
    writeln(outf, i);
    goto ex;
 
    next:
  end;
 
ex:
 
close(inf);
close(outf);
end.

Помогите, для больших массивов по времени не проходит, как можно оптимизировать?

@Puporev · 26.02.2011, 19:55

Может вообще без массивов обойтись? Зачем он нужен. Читай файл и ищи...

@iama · 26.02.2011, 20:45 **[ТС]**

Puporev, это сильно ускорит работу программы

Добавлено через 40 минут
решил, тема закрыта

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	26.02.2011, 19:55
	Может вообще без массивов обойтись? Зачем он нужен. Читай файл и ищи... 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	26.02.2011, 20:45 [ТС]
	Puporev, это сильно ускорит работу программы Добавлено через 40 минут решил, тема закрыта 0