如何当尺寸被缩短

保持为数组的最大值假设我们有一个数组A [0：Ñ -1]在大小n和int maxElem其保持A的最大值[i：n -1]，其中i在开始处被初始化为0，然后在每个步骤中被加1。如何当尺寸被缩短

那么如何保持这个时间复杂度为O（n）？一种简单的方法是在最大搜索在A [我：Ñ -1]中的每一步，这样我从0到Ñ -1，我们要做的（Ñ -1）+ （n -2）+ ... + 0 = O（n^2）次搜索，它看起来太耗时。有没有人知道比这种方法更好的算法？

来源

2015-09-06 yanyupeng

提供您所使用的语言，你已经尝试什么中最大。堆栈溢出是针对特定的编程问题，而不是理论情况。 – deezy

明白了。下次将附上代码。谢谢。 – yanyupeng

您已经计算了[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]

来源

2015-09-06 01:43:59 coderredoc

如何当尺寸被缩短

回答

相关问题