找到所有子陣列中最大值的總和

-2

問題是 - 找到所有子陣列中所有最大值的總和。例如，我有數組{2，8,4，3，5}，該解決方案將是在哪裏92.所有我的子陣列的有：找到所有子陣列中最大值的總和

{2}，{8}，{4}，{3 }，{5}，

{2,8}，{8,4}，{4,3}，{3,5}，

{2,8,4}，{8,4 ，3}，{4,3,5}，

{2,8,4,3}，{8,4,3,5}，

{2,8,4,3,5 }

並且所有子陣列的所有最大值是：

2 - 8 - 4 - 3 - 5 -

8 - 8 - 4 - 5 -

8 - 8 - 5 -

8 - 8 -

你知道在線性時間複雜度下解決這個問題的方法嗎？

來源

2017-09-26 Rik4chu

是的，我們知道。但你的嘗試是什麼？任何代碼與你糾纏？ –

問題是你是如何解決它的。 –

嗯，我試圖在n^2中解決這個問題，找到所有的子數組，並從每一箇中獲得最大值，但不幸的是，這裏的關鍵是嘗試在線性時間內解決這個問題 – Rik4chu

它應該是非常簡單的。請參閱以下算法

sum = 0 
max = 0 
for every array 'arr' in the array of arrays 
do 
    for every element 'arri' in the array 'arr' 
    do 
     if arri >= max, max = arri 
    end for 
    max = 0 
    sum = sum + max 
end for

來源

2017-09-26 20:23:48 VHS

感謝您的回答，但不幸的是我無法在n^2複雜時間內解決這個問題。我必須在線性時間內解決這個問題。 – Rik4chu

這不是n^2的複雜性。這只是n。 – VHS

但是從數組中獲取所有的子數組需要n，並且從每個子數組中獲取值取其他n，所以這是n^2。在你的代碼中你有兩個for，這表示你在n^2中嘗試這個。 – Rik4chu

找到所有子陣列中最大值的總和

回答

相關問題