arrays - 最高百分比增加

Question

假设我们有以下一组数字表示随时间变化的值

1 2 3 10 1 20 40 60

现在我正在寻找一种算法来找到从一个时间到另一个时间的最高百分比增长。在上述情况下，答案是 (1, 60) 对，增加了 6000%。

到目前为止，我能想到的最好的算法是暴力法。我们使用一系列迭代来考虑所有可能的对:

第一次迭代:

1-2 1-3 1-10 .. 1-60

第二次迭代

 2-3 2-10 2-1 ... 2-60

(等)

复杂度为 O(n³)。

我也一直在考虑另一种方法。找出所有严格递增的序列，并只确定这些严格递增序列的百分比增加。

你们还有其他想法吗？如果我的想法有误，请指正!

Answer 1

我可能误解了这个问题，但似乎您想要的只是最大和最小的数字，因为这两个数字很重要。

while true:
    indexOfMax = max(list)
    indexOfMin = min(list)
    list.remove(indexOfMax)
    list.remove(indexOfMin)
    if(indexOfmax < indexOfMin)
        contine
    else if(indexOfMax == indexOfMin)
        return -1
    else
        SUCCESS