algorithm - 在小于 O(n^2) 的情况下最大化给定方程

Question

给定一个数组如何找到最大值

    (ar[j]-ar[i]-1)*(min(ar[i],ar[j]))

时间为 O(n) 或 O(nlogn)

Answer 1

如果输入总是非负的，那么除了 ar 的最大元素之外没有任何意义作为ar[j] ;任何不使用 ar[j] 的产品可以通过使用 ar[j] 来增加.因此，我们可以在 O(n) 中找到最大值时间并针对 ar[i] 的所有可能值进行尝试在 O(n)是时候解决问题了。

如果不要求输入非负，最大乘积必须使用最大ar[j]或最小 ar[j] .同样，我们可以找到最大值和最小值，并针对所有可能的 ar[i] 进行尝试值(value)观。