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)，所以你很好。