最大化arr[i]*i之和

Question

我得到了一个数组

arr

，需要最大化

arr[i]*i

。 https://www.geeksforgeeks.org/maximize-sum-arrii给出的一个简单解决方案是对数组进行排序，然后求和。但是，我该如何确认最终的总和在所有可能的答案中是最大的这一事实。

Answer 1

我想这个问题太老了，但是作为一个数学证明，为什么结果总和将是最大值是由重排不等式保证的。这是其声明和证明的链接在精彩页面，现在将其应用到我们知道的这种情况下
n - 1 > n - 2 > n -3 > ... > 0 并且在按升序对数组进行排序后我们知道 arr[n - 1] ≥ arr[n - 2] ≥ arr[n - 3] ≥ ... ≥ arr[0] 现在应用不等式，瞧你得到 Σi * arr[i]
的最大值

PS：在不等式的联系中，π(x)用更简单的术语来说就是数组的所有可能的排列或以数学方式的排列，它们恰好是 n 阶乘或 n!。要了解更多信息，您可以查看此链接