选择正确的算法

Question

我有这个问题：
有一个 N 元素的整数向量，我称之为 A.
然后有两个元素，我称它们为 (P,Q)，这样 0<= P <= Q <N（P,Q 是 A 的索引）。
我们使用这两个元素来计算 L = A[P] + A[Q] + (Q-P).

我必须使用复杂度为 O(n) 的算法并使用 O(1) 内存来计算 L 的最大值。

这是我的解决方案，但我认为它是 O(n^2):

int L = 0;

for(int i=0; i<A.size(); i++) {
  for(int j=i; j<A.size(); j++) {
    L = max(L, A[i] +A[j] +(j-i) );  
  }
}

cout<<"Best: "<<L<<endl;

你有更好的算法来解决这个问题吗？

编辑
这是一个简单的例子：

A = [-8,4,0,5,-3,6]

结果应该是L = 14( A[1] +A[5] +(5-1) )

最终解决方案

int solve_A_2_002(const std::vector<int>& A) {
    int P = A[0];
    int P_i = 0; //index

    int Q = A[0];
    int Q_i = 0;

    int L = P+P;

    int temp1,temp2, temp3;

    for(int i=0; i<A.size(); i++) {
        temp1 = A[i] + P + (i - P_i);
        temp2 = A[i] + Q + (i - Q_i);
        temp3 = A[i] + A[i];

        if(L < temp1) {
            L = temp1;
            Q_i = i; //save new couple (P,Q)
            Q = A[i];
        }

        if(L < temp2) {
            L = temp2;
            P_i = i;
            P = A[i];
        }

        if(L < temp3) {
            L = temp3;
            P_i = Q_i = i;
            Q = P = A[i];

        }
    }

    return L;
}

Answer 1

当你用两个变量的所有组合做某事但仍然想要次二次时间时，一个常见的事情是尝试将你正在做的事情分成两部分一个-可变的东西。

在这种情况下，这很简单：

L = (A[P] - P) + (A[Q] + Q);

我们显然可以通过最大化这两个部分来在线性时间和常量内存中最大化这个数量。但是我们显然可以解决的问题是一个简化的问题：真正的问题有一个额外的约束 P <= Q.

一般来说，我们必须做更多的工作来获取我们可以简单计算的东西并将它们组合起来以产生我们想要的问题的答案。有时，这种进一步的分析可能会有些复杂，或者需要一些巧妙的方法来将我们可以轻松计算的事物组合成我们真正关心的问题的解决方案。

虽然在这种情况下，我们可以轻松解决 的简化问题的解决方案是 原始问题的解决方案。一个简单的方法是写

A[x] - x = (A[x] + x) - 2x

从中不难看出，如果x=Q是一个最大化A[x] + x的值，那么x>Q必然会产生一个较小的A[x] - x值。

Answer 2

无法真正证明它（这里已经晚了），但算法应该将第一个元素作为 P 和 Q, (P=0, Q=0 )，并迭代数组的其余部分，并为每个元素 E 计算仅三对 (P, E)、(Q, E) 和 (E, E) 的 L。如果其中一个比旧的 (P, Q) 大，则将那对作为新的 P 和 Q.

选择正确的算法

Choose the right algorithm

c++

algorithm

big-o