Just for fun, I'm trying to solve UVA 11078 (Open Credit System). (Solutions can be checked on vjudge.net)
The goal is to find a maximum consecutive difference for a given list of integers:
For example: given this list of four numbers: 7 10 3 1
the maximum consecutive difference is 9
, since 10 - 1 = 9
.
In the problem, first a number of testcases T
is given, then the amount of numbers n
, and then the individual numbers. This input (with T = 2
, first n = 4
and then n = 2
) for example
2
4
7
10
3
1
2
100
20
would result in two testcases, one of 4 numbers (7 10 3 1
) and one of 2 numbers (100 20
). Output of this should be:
9
80
I implemented the following Python program, and I would think this would have complexity O(n) since it goes through each number only once, but still UVA is giving me Time Limit Exceeded.
import math
T = int(input())
for _ in range(T):
n = int(input())
diff = -math.inf
score = int(input()) # Using the very first input as max and min
max = score
min = score
for i in range(1,n):
score = int(input())
if max - score > diff:
diff = max - score
if score > max:
max = score
if score < min:
min = score
print(diff)
How can I improve this solution? I have seen other solutions to this problem, but I'm somewhat confused to why this solution would be slow...
Adding this at the top sufficed:
import sys
input = sys.stdin.__next__
You could also remove the min
stuff, since you're not using it, use map(int, sys.stdin)
and iterate that with next
and islice
instead of the slow range
, try float instead of int, and put the whole code inside a function to benefit from faster variables. But the judge seems rather unstable (gave me 540 and 200 ms for the same solution), making benchmarking such optimizations rather impossible.