最大化总和，距离整数数组 [英] Maximize sum-distance for integer array

问题描述

给定一个整型数组A，返回两个元素之间的最大可能的总和距离。总和距离被定义为 A [I] + A [J] +（I - J）对于i>Ĵ

Given an integer array A, return the maximum possible sum-distance between two elements. The sum-distance is defined as A[i] + A[j] + (i - j) for i > j

例如与 A = [8,2，4，9，5，8，0，3，8，2] 最大总和，距离为24取得其中i = 0和j = 8

For example with A = [8, 2, 4, 9, 5, 8, 0, 3, 8, 2] the max sum-distance is 24 achieved with i=0 and j=8

这是O（ N ² ）解决方案实在是微不足道。是否有任何O（ N ）解决方案（其中的 N 是数组的长度）？

An O(n²) solution is trivial. Is there any O(n) solution (where n is the length of the array)?

推荐答案

这是可能的：

• 创建一个数组，并与A [I]填充+我对每个i

• Create an array and fill it with A[i]+i for each i

创建另一个数组并用[J]填充 - J对每个j

Create another array and fill it with A[j] - j for each j

获取最高的索引我[MAXI]和J [MAXJ]

Get the indexes with the highest I[maxI] and J[maxJ]

返回A [MAXI] + A [MAXJ] +马克西 - MAXJ

return A[maxI] + A[maxJ] + maxI - maxJ

你去那里，O（N）！

这篇关于最大化总和，距离整数数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！