在小于 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)时间内找到最大值，并在O(n)时间内与ar[i]的所有可能值进行尝试以解决问题。

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