algorithm - 如何在缩短大小时保持数组中的最大值

Question

假设我们有一个大小为 n 的数组 A[0:n-1] 和一个保持 A[i< 的最大值的整数 maxElem/em>:n-1]，其中i在开始时被初始化为0，然后每一步加1。

那么如何在 O(n) 的时间复杂度内维护这个 maxElem 呢？一个简单的方法是在每一步中搜索 A[i:n-1] 中的最大值，因此 i 从 0 到 n -1，我们必须做 (n-1)+(n-2)+...+0 = O(n^2) 次搜索，看起来太耗时了。有谁知道与此方法相比更好的算法吗？

Answer 1

您已经为 [i..n-1] 计算了，那么您不需要重新考虑 [i ..n-1] 中的所有值再次在 [i-1 i ... n-1] 中。所以更好的算法是

+ get an array max_from[0..n-1]
+ set i=n-1;
+ max_from[n-1]= A[n-1];
+ for i=n-2 downto 0
    if(A[i]>max_from[i+1])
      max_from[i]=max_from[i+1];
    else
      max_from[i]=A[i];

Time_comlexity-O(n) Space-complexity-O(n)

max_from[i]==> 元素A[i],A[i+1],...,A[n-1]中的最大值