Troublesome Frog (AIO Intermediate 2013) 3.x

Question

Recently I was trying out this problem and my code got 60% of the marks, with the remaining cases returning TLEs.

Bazza and Shazza do not like bugs. They wish to clear out all the bugs on their garden fence. They come up with a brilliant idea: they buy some sugar frogs and release them near the fence, letting them eat up all the bugs.

The plan is a great success and the bug infestation is gone. But strangely, they now have a sugar frog infestation. Instead of getting rid of the frogs, Bazza and Shazza decide to set up an obstacle course and watch the frogs jump along it for their enjoyment.

The fence is a series of \$N\$ fence posts of varying heights. Bazza and Shazza will select three fence posts to create the obstacle course, where the middle post is strictly higher than the other two. The frogs are to jump up from the left post to the middle post, then jump down from the middle post to the right post. The three posts do not have to be next to each other as frogs can jump over other fence posts, regardless of the height of those other posts.

The difficulty of an obstacle course is the height of the first jump plus the height of the second jump. The height of a jump is equal to the difference in height between it's two fence posts. Your task is to help Bazza and Shazza find the most difficult obstacle course for the frogs to jump.

Input
Your program should read from the file. The file will describe a single fence.

The first line of input will contain one integer \$N\$: the number of fence posts. The next \$N\$ lines will each contain one integer \$h_i\$: the height of the ith fence post. You are guaranteed that there will be at least one valid obstacle course: that is, there will be at least one combination of three fence posts where the middle post is strictly higher than the other two.

Output
Your program should write to the file. Your output file should contain one line with one integer: the greatest difficulty of any possible obstacle course.

Constraints
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

\$3 \leq N \leq 100,000\$ (the number of fence posts)
\$1 \leq h_i \leq 100,000\$ (the height of each post)

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular:

For 30% of the marks, \$N \leq 300\$. For an additional 30% of the marks, \$N \leq 3,000\$. For the remaining 40% of the marks, no special > constraints apply.

Hence, I was wondering if anyone could think of a way to optimize my code (below), or perhaps provide a more elegant, efficient algorithm than the one I am currently using.

Here is my code:

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() 

If you require additional information regarding my solution or the problem, please do comment below.

Answer 1

Without going into the algorithm I see a few things that could be improved upon

1. Use with open(...) as ... instead of manually opening and closing
2. Use max() instead of the ... if ... else ... structure
3. Improve naming of your variables, PEP8 is a good guideline
4. Use if __name__ == __main__:
5. List comprehension at reading input

---

def froggin(fences):
    maximum = 0
    for idx in range(1, N - 1):
        left = min(fences[0: idx])
        right = min(fences[idx + 1:])
        middle = fences[idx]

    if left < middle and right < middle:
        new_max = middle - left + middle - right
        maximum = max(new_max, maximum)
    return maximum

if __name__ == '__main__':
    with open('frogin.txt', 'r') as infile:
        N = int(infile.readline())
        fences = [int(infile.readline()) for _ in range(N)]

    result = froggin(fences)

    with open('frogout.txt', 'w') as frogout:
        frogout.write(str(result))

Answer 2

#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]

I find the variable naming a bit counterintuitive: why not name the variables in order and require x < y > z?

But more importantly, the two min calls between them take \$\Theta(N)\$ time, so the entire loop takes \$\Theta(N^2)\$ time. It would be asymptotically better to pre-calculate lists which give the minimum value in each prefix and suffix, because then the whole thing can be done in time \$\Theta(N)\$.