python - 更好的 python 逻辑可以防止在嵌套循环中比较数组时超时

Question

我试图解决一个编程挑战，我编写的程序正确地解决了这个问题的小测试数据。但是当他们针对更大的数据集运行它时，我的程序有时会超时。我主要是一个自学成才的程序员，如果有比我的逻辑更好的算法/实现，你们能告诉我吗。谢谢。

问题

Given an array of integers, a, return the maximum difference of any pair of numbers such that the larger integer in the pair occurs at a higher index (in the array) than the smaller integer. Return -1 if you cannot find a pair that satisfies this condition.

我的 Python 函数

def maxDifference( a):
    diff=0
    find=0
    leng = len(a)
    for x in range(0,leng-1):
        for y in range(x+1,leng):
            if(a[y]-a[x]>=diff):
                  diff=a[y]-a[x]
                  find=1
    if find==1:
        return diff
    else:
        return -1

约束:

1 <= N <= 1,000,000
-1,000,000 <= a[i] <= 1,000,000 i belongs to [1,N]

示例输入:

Array { 2,3,10,2,4,8,1}

示例输出:

8

Answer 1

好吧...因为您只关心在最小数之后找到最大数，只要差异是迄今为止最大的，就没有理由进行多次传递或使用 max() 在数组的一部分上:

def f1(a):
    smallest = a[0]
    result = 0
    for b in a:
        if b < smallest: 
            smallest = b
        if b - smallest > result:
            result = b - smallest

    return result if result > 0 else -1

感谢@Matthew 的测试代码:)即使在大集合上也非常快:

The maximum difference is 99613 99613 99613
Time taken by Sojan's method: 0.0480000972748
Time taken by @Matthews's method: 0.0130000114441
Time taken by @GCord's method: 0.000999927520752