Find which two values in an array maximize a given expression?

Question

I met a very simple interview question, but my solution is incorrect. Any helps on this? 1)any bugs in my solution? 2)any good idea for time complexity O(n)?

Question:

Given an int array A[], define X=A[i]+A[j]+(j-i), j>=i. Find max value of X?

My solution is:

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;
}

Answer 1

The crucial insight is that it can be done in O(n) only if you track where potentially useful values are even before you're certain they'll prove usable.

Start with best_i = best_j = max_i = 0. The first two track the i and j values to use in the solution. The next one will record the index with the highest contributing factor for i, i.e. where A[i] - i is highest.

Let's call the value of X for some values of i and j "X_i,j", and start by recording our best solution so far ala X_best = X_0,0

Increment n along the array...

• whenever the value at [n] gives a better "i" contribution for A[i] - i than max_i, update max_i.

• whenever using n as the "j" index yields X_{max_i,n} greater than X_best, best_i = max_i, best_j = n.

Discussion - why/how it works

j_random_hacker's comment suggests I sketch a proof, but honestly I've no idea where to start. I'll try to explain as best I can - if someone else has a better explanation please chip in....

Restating the problem: greatest X_i,j where j >= i. Given we can set an initial X_best of X_0,0, the problem is knowing when to update it and to what. As we contemplate successive indices in the array as potential values for j, we want to generate X_i,j=n for some i (discussed next) to compare with X_best. But, what i value to use? Well, given any index from 0 to n is <= j, the j >= i constraint isn't relevant if we pick the best i value from the indices we've already visited. We work out the best i value by separating the i-related contribution to X from the j-related contribution - A[i] - i - so in preparation for considering whether we've a new best solution with j=n we must maintain the best_i variable too as we go.

A way to approach the problem

For whatever it's worth - when I was groping around for a solution, I wrote down on paper some imaginary i and j contributions that I could see covered the interesting cases... where Ci and Cj are the contributions related to n's use as i and j respectively, something like

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

You'll notice I didn't bother picking values where Ci could be A[i] - i while Cj was A[j] + j... I could see the emerging solution should work for any formulas, and that would have just made it harder to capture the interesting cases. So - what's the interesting case? When n = 2 the Ci value is higher than anything we've seen in earlier elements, but given only knowledge of those earlier elements we can't yet see a way to use it. That scenario is the single "great" complication of the problem. What's needed is a Cj value of at least 9 so Xbest is improved, which happens to come along when n = 4. If we'd found an even better Ci at [3] then we'd of course want to use that. best_i tracks where that waiting-on-a-good-enough-Cj value index is.

Answer 2

Longer version of my comment: what about iterating the array from both ends, trying to find the highest number, while decreasing it by the distance from the appripriate end. Would that find the correct indexes (and thus the correct X)?

#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
#include <climits>

long long brutal(const std::vector<int>& a) {
    long long x = LLONG_MIN;
    for(int i=0; i < a.size(); i++)
        for(int j=i; j < a.size(); j++)
            x = std::max(x, (long long)a[i] + a[j] + j-i);
    return x;
}

long long smart(const std::vector<int>& a) {
    if(a.size() == 0) return LLONG_MIN;
    long long x = LLONG_MIN, y = x;
    for(int i = 0; i < a.size(); i++)
        x = std::max(x, (long long)a[i]-i);
    for(int j = 0; j < a.size(); j++)
        y = std::max(y, (long long)a[j]+j);
    return x + y;
}

int main() {
    std::random_device rd;
    std::uniform_int_distribution<int> rlen(0, 1000);
    std::uniform_int_distribution<int> rnum(INT_MIN,INT_MAX);
    std::vector<int> v;
    for(int loop = 0; loop < 10000; loop++) {
        v.resize(rlen(rd));
        for(int i = 0; i < v.size(); i++)
            v[i] = rnum(rd);
        if(brutal(v) != smart(v)) {
            std::cout << "bad" << std::endl;
            return -1;
        }
    }
    std::cout << "good" << std::endl;
}