数组中两个元素的最大和减去它们之间的距离
数组中两个元素的最大和减去它们之间的距离
提问于 2020-03-09 03:56:46
我试图找出数组中两个元素的最大和减去它们之间的距离。具体地说，我正在尝试计算max{ ai+aj-|i-j| }我现在卡住了。我显然考虑过天真的方法(O(n^2))。然而，我非常确定有一种更好、更有效的方法(O(nlogn))甚至O(n)。有没有人能帮我解决这个问题？如果有人提出一些提示或简单的想法来开始一些事情，我将不胜感激。是否先对数组进行排序？也许使用动态编程方法？
编辑:我想我已经找到了一个O(n)解，让我们假设我们的最大和来自ai和aj，ai对这个和的贡献是: ai+i。aj与aj-j一起贡献了这笔款项。(因为我们的和是ai+aj-|j-i|= ai+aj+i-j。)方法:为方便起见，我们计算矩阵A_plus_index=ai+i和A_minus_index=ai-i。然后我们使用两个辅助数组: i)第一个对每个i都有，这是只考虑从0到i的元素的A_plus_index数组的最大值。ii)第二个对每个i有，只考虑从N到i的元素的A_minus_index数组的最大值，其中N是数组a的长度。现在我们遍历一次数组，找到最大值: A_plus_indexi+ A_minus_indexi+1。总复杂度O(n)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-03-09 20:42:22
@JeffersonWhite你的想法行得通，你可以把它作为答案发布并接受它。
但我会对你的想法稍加改进：
您只能构建一个数组，而不是2个，该数组包含到目前为止从N-1到1的每个j的最大A[j] - j。
然后在每次计算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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60591517
复制相关文章
相似问题
腾讯云开发者
