5

给定一个整数数组,我必须找出任何两个元素之间的最大差异,以便在数组中较小的数字之后出现较大的数字。我使用了一种简单的方法,并通过保持与迄今为止遇到的最小数字的差异两件事的轨迹

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;

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

4

1 回答 1

6

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

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

于 2013-04-05T14:22:55.833 回答