Проблемная лягушка AIO 2013 Промежуточный Python 3.x ⇐ Python

[Anonymous]

Недавно я попробовал эту проблему, и мой код получил 60% отметок, а оставшиеся случаи возвращали TLE. < /p>


Bazza и Shazza не любят ошибки. Они хотят очистить все ошибки
на их садовом заборе. Они придумывают блестящую идею: они покупают
немного сахарных лягушек и освобождают их возле забора, позволяя им съесть
все ошибки. Но
, как ни странно, у них теперь есть заражение сахарной лягушкой. Вместо того, чтобы избавиться от лягушек, Bazza и Shazza решают настроить полосу препятствий
и посмотреть, как лягушки прыгают вдоль его для удовольствия. Bazza и
Shazza выберут три поста для забора, чтобы создать полосу препятствий,
, где средний пост строго выше, чем у двух других. Лягушки
должны прыгать с левого поста на средний пост, а затем спрыгнуть вниз
с среднего поста в правый пост. Три поста не должны
рядом друг с другом, так как лягушки могут перепрыгивать через другие посты забора,
независимо от высоты этих других постов. Высота прыжка равна
разницу в высоте между его двумя ограждениями. Ваша задача состоит в том, чтобы
помочь Bazza и Shazza найти самую сложную полосу препятствий для лягушек
для прыжков. Файл будет описать
один забор. Следующие строки \ $ n \ $ будут содержать одно целое число \ $ h_i \ $:
высота поста забора ITH. Вам гарантируется, что будет состоится
меньше всего действительного курса препятствий: то есть, будет, по крайней мере, одна комбинация
из трех постов забора, в которой средняя пост строго
выше, чем два других. Ваш выходной файл должен
содержать одну строку с одним целым числом: наибольшая сложность любого
возможное препятствие. Все эти файлы будут придерживаться следующих границ: < /p>

\ $ 3 \ leq n \ leq 100 000 \ $ (количество постов забора)

\ $ 1 \ leq h_i \ leq 100 000 \ $ (высота каждого поста) < /p>

как некоторые тестируемые случаи будут в целом. Подумайте о том, насколько хорошо масштабируется ваше решение для более крупных входных значений
. Однако не все случаи будут большими. В частности: < /p>

за 30% отметок, \ $ n \ leq 300 \ $. Для дополнительных 30% от Marks
\ $ n \ leq 3000 \ $. Для оставшихся 40% оценок не применяются специальные> ограничения. />
infile = open('frogin.txt', 'r')
outfile = open('frogout.txt', 'w')

N = int(infile.readline())

l = []

for i in range(N):
l.append(int(infile.readline()))

m = 0
#find maximum z-x+z-y such that the middle number z is the largest of x, y, z
for j in range(1, N - 1):
x = min(l[0: j])
y = min(l[j + 1:])
z = l[j]
if x < z and y < z:
n = z - x + z - y
m = n if n > m else m

outfile.write(str(m))

infile.close()
outfile.close()
exit()
< /code>

Если вам требуется дополнительная информация о моем решении или проблеме, пожалуйста, прокомментируйте ниже. < /p>

Подробнее здесь: https://stackoverflow.com/questions/459 ... python-3-x