pythonperformance

Time Limit Exceed on a UVA problem using Python, is this code that inefficient?


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


Solution

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