如何找到给定数组的最大跨度？

Question

我试图解决的问题如下：我想在给定的数组中找到一个最大的数字跨度，该数组由正整数和负整数组成，返回最大值（a[j]-a[I]），这样1

1. 求数组的n阶统计量的索引，使其为“i”

这个算法是O（nlogn），但我不知道它是否正确。

Answer 1

这是一个O（n）算法。

1. 构建一个数组Max，其中Max[i]是k的A[k]的最大值

编辑时：有一个角情况，其中数组的顺序是反向排序的，在这种情况下，所有i的Max[i]=Min[i]=A[i]。这可以在O（n）时间内检测到，在这种情况下，您只需返回最大化A[i 1]-A[i]的一对相邻元素（这将是负数）。

Answer 2

@mrip解决方案的时间复杂度为O（n），空间复杂度为O（n）。这是正确的，但是对于这个问题，只有O（1）空间复杂度就足够了。

int min=a[0],ans=0;
for (int i=1;i<n;i++)
    if (a[i]<min) min=a[i];
    else ans=max(ans,a[i]-min);
return ans;