找到所有子阵列中最大值的总和

问题描述：

问题是 - 找到所有子阵列中所有最大值的总和。例如，我有数组{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 -

你知道在线性时间复杂度下解决这个问题的方法吗？

是的，我们知道。但你的尝试是什么？任何代码与你纠缠？ –

问题是你是如何解决它的。 –

嗯，我试图在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

感谢您的回答，但不幸的是我无法在n^2复杂时间内解决这个问题。我必须在线性时间内解决这个问题。 – Rik4chu

这不是n^2的复杂性。这只是n。 – VHS

但是从数组中获取所有的子数组需要n，并且从每个子数组中获取值取其他n，所以这是n^2。在你的代码中你有两个for，这表示你在n^2中尝试这个。 – Rik4chu

找到所有子阵列中最大值的总和

相关推荐