如何當尺寸被縮短

保持爲數組的最大值假設我們有一個數組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

如何當尺寸被縮短

回答

相關問題