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.
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.
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.
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.