c - 两个元素之间的最大差异

Question

给定一个整数数组，我必须找出任意两个元素之间的最大差值，使得较大的数字出现在数组中较小的数字之后。我使用了一种简单的方法，并求出与遇到的最小数字的差值，所以远不止跟踪两件事

1.最大差值

2.到目前为止访问的最小数量。

    int min_element=arr[0];
    int diff=arr[1]-arr[0];
    for(i=1;i<n;i++)
    {
        if(arr[i]-min_element>diff)
            diff=arr[i]-min_element;
        if(arr[i]<min_element)
            min_element=arr[i];
    }
    return diff;

有没有更好的方法来解决这个问题？

Answer 1

就目前而言，您的算法是最优的，直到一个常数因子。

读取 n 整数数组需要 Ω(n)。你的算法是 O(n)，所以你很好。