数组中两个元素的最大和减去它们之间的距离 [英] Maximum sum of two elements in an array minus the distance between them

问题描述

我试图找到一个数组中两个元素的最大和减去它们之间的距离.具体来说，我正在尝试计算max {a [i] + a [j]-| i-j |}我目前陷入困境.我显然已经考虑过幼稚的方法(O(n ^ 2)).但是，我很确定有更好，更有效的方法(O(nlogn))甚至O(n).有人可以帮助我解决问题的方法吗?如果有人提出任何提示或简单的想法以开始工作，我将不胜感激.首先对数组进行排序?也许使用动态编程方法?

I am trying to find the maximum sum of two elements in an array minus the distance between them. Specifically I am trying to calculate max{ a[i]+a[j]-|i-j| } I am currently stuck. I have obviously considered the naive approach (O(n^2)). However ,I am pretty sure there is a better ,more efficient approach (O(nlogn)) or even O(n). Can someone please help me on how to approach the problem. I would be grateful if anyone threw some hints or a simple idea to have something to start from. Sorting the array first? Maybe using a dynamic programming approach?

我想我已经找到了O(n)解决方案假设我们的最大和来自a [i]和a [j]，a [i]贡献了该和:a [i] + i.a [j]通过a [j] -j对该总和作出贡献.(因为我们的总和为a [i] + a [j]-| j-i | = a [i] + a [j] + i-j.)方法:为方便起见，我们计算矩阵A_plus_index = a [i] + i和A_minus_index = a [i] -i.然后，我们使用两个帮助数组:i)第一个对于每个i具有A_plus_index数组的最大值，仅考虑从0到i的元素.ii)第二个对于每个i，仅考虑从N到i的元素，A_minus_index数组的最大值，其中N是数组a的长度.现在，我们遍历一次数组并找到最大值:A_plus_index [i] + A_minus_index [i + 1].总复杂度O(n).

I think I have found an O(n) solution Let's assume that our max sum comes from a[i] and a[j] , a[i] contributes to that sum with : a[i]+i . a[j] contributes to that sum with a[j]-j. (Because our sum is a[i]+a[j]-|j-i|= a[i]+a[j]+i-j. ) Approach: for convenience we compute the matrices A_plus_index=a[i]+i and A_minus_index=a[i]-i. Then we use two helping arrays: i) The first one has for every i ,the max value of A_plus_index array considering only the elements from 0 to i. ii) The second has for every i, the max value of A_minus_index array considering only the elements from N to i ,where N is the length of array a. Now we traverse the arrays once and find the max: A_plus_index[i]+ A_minus_index[i+1]. Total complexity O(n).

推荐答案

@JeffersonWhite，您的想法行得通，您可以将其发布为答案并接受.

@JeffersonWhite your idea works and you could post it as an answer and accept it.

但是我将对您的想法进行一些改进:

But I am going to improve upon your idea a little bit:

您只能构建一个数组，而不是2，因为到目前为止，对于 N-1中的每个 j ，该数组都包含最大的 A [j]-j 转换为 1 .

You could build only one array instead of 2, which contains the maximum of A[j] - j so far for each j from N-1 to 1.

然后每次计算 max(A [i] + i + max_so_far-_reverse [i + 1])

//Building the reverse array
max_so_far_reverse = array of length N
max_reverse = A[N-1]-(N-1)
max_so_far_reverse[N-1] = max_reverse
for j = N-2 to 1:
   max_reverse = max(max_reverse, A[j]-j)
   max_so_far_reverse[j] = max_reverse

//Computing maximum value by traversing forward
max = 0
for i = 0 to N-2:
    max = max(max, A[i] + i + max_so_far_reverse[i+1])

return max

这篇关于数组中两个元素的最大和减去它们之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！