c++ - 查找数组中的两个值使给定表达式最大化？

我遇到了一个非常简单的面试问题，但解决方案不正确。有什么帮助吗？ 1)我的解决方案中有任何错误？ 2)关于时间复杂度O(n)有什么好主意吗？

问题:

给定一个int数组A[]，定义X=A[i]+A[j]+(j-i), j>=i。查找X的最大值？

我的解决方案是:

int solution(vector<int> &A){
    if(A.empty())
        return -1;
    long long max_dis=-2000000000, cur_dis;
    int size = A.size();
    for(int i=0;i<size;i++){
        for(int j=i;j<size;j++){
            cur_dis=A[j]+A[i]+(j-i);
            if(cur_dis > max_dis)
                max_dis=cur_dis;
        }
    }
    return max_dis;
}

最佳答案

至关重要的见解是，只有在您确定潜在有用的值将证明可用之前，才可以在O(n)中完成此操作。

从best_i = best_j = max_i = 0开始。前两个跟踪解决方案中使用的i和j值。下一个将记录对i具有最高影响因子的索引，即A[i] - i最高的索引。

让我们将i和j的某些值的X值称为“Xi，j”，并从记录迄今为止的最佳解决方案开始ala Xbest = X0,0

沿数组递增n ...

只要[n]的值对A[i] - i的“i”贡献大于max_i，请更新max_i。

每当将n用作“j”索引时，

都会产生大于Xbest的Xmax_i，n，best_i = max_i，best_j = n。

讨论-为什么/如何运作

j_random_hacker的评论建议我草绘一个证明，但老实说，我不知道从哪里开始。我将尽力解释-如果其他人有更好的解释，请加入...。

重述问题:最大的Xi，j，其中j> = i。假设我们可以将初始Xbest设置为X0,0，那么问题就在于何时更新它以及更新到什么。当我们考虑将数组中的连续索引作为j的潜在值时，我们想为某些i(接下来讨论)生成Xi，j = n以便与Xbest进行比较。但是，我最喜欢使用什么？好吧，给定从0到n的任何索引都是 = i约束将不相关。我们通过将与i有关的贡献与与j有关的贡献-A[i] - i分开来计算出最佳i值，因此在考虑是否有j = n的新最佳解决方案时，我们也必须保持best_i变量，例如我们去。

解决问题的方法

无论什么值(value)-当我四处寻找解决方案时，我在纸上写下了一些虚构的i和j贡献，我可以看到它们涵盖了有趣的情况...其中Ci和Cj是与n用作i和j分别，像

n    0  1 2  3 4
Ci   4  2 8  3 1
Cj   12 4 3  5 9

您会注意到，我没有理会在Ci可能为A [i]-i而Cj为A [j] + j的情况下选择值的情况。我可以看到新兴的解决方案适用于任何公式，使得捕获有趣的案例变得更加困难。所以-有趣的情况是什么？当n = 2时，Ci值高于我们在早期元素中看到的值，但仅了解那些早期元素，我们尚无法找到使用它的方法。这种情况就是问题的唯一“巨大”复杂性。所需的Cj值至少为9，因此Xbest会得到改善，当n = 4时会出现。如果我们在[3]处找到更好的Ci，那么我们当然想使用它。 best_i跟踪等待足够好的Cj值索引所在的位置。