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

Answer 3

I'll write in pseudo code because I don't have much time, but this should be the most performing way using recursion

compare(array, left, right)

val = array[left] + array[right] + (right - left);

if (right - left) > 1
  val1 = compare(array, left, right-1);
  val2 = compare(array, left+1, right);

  val = Max(Max(val1,val2),val);
end if

return val

and than you call simply

compare(array,0,array.length);

I think I found a incredibly faster solution but you need to check it:

you need to rewrite your array as follow

Array[i] = array[i] + (MOD((array.lenght / 2) - i));

Then you just find the 2 highest value of the array and sum them, that should be your solution, almost O(n)

wait maybe I'm missing something... I have to check.

Ok you get the 2 highest value from this New Array, and save the positions i, and j. Then you need to calculate from the original array your result.

------------ EDIT

This should be an implementation of the method suggested by Tony D (in c#) that I tested.

        int best_i, best_j, max_i, currentMax;

        best_i = 0;
        best_j = 0;
        max_i = 0;
        currentMax = 0;

        for (int n = 0; n < array.Count; n++)
        {
            if (array[n] - n > array[max_i] - max_i) max_i = n;

            if (array[n] + array[max_i] - (n - max_i) > currentMax)
            {
                best_i = max_i;
                best_j = n;
                currentMax = array[n] + array[max_i] - (n - max_i);
            }

        }

        return currentMax;

Answer 4

Question:

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

Answer O(n):

lets rewrite the formula: X = A[i]-i + A[j]+j

we can track the highest A[i]-i we got and the highest A[j]+j we got. We loop over the array once and update both of our max values. After looping once we return the sum of A[i]-i + A[j]+j, which equals X.

We absolutely don't care about the j>=i constraint, because it is always true when we maximize both A[i]-i and A[j]+j

Code:

int solution(vector<int> &A){
    if(A.empty()) return -1;

    long long max_Ai_part =-2000000000;
    long long max_Aj_part =-2000000000;
    int size = A.size();

    for(int i=0;i<size;i++){
        if(max_Ai_part < A[i] - i)
            max_Ai_part = A[i] - i;
        if(max_Aj_part < A[j] + j)
            max_Ai_part = A[j] - j;
    }

    return max_Ai_part + max_Aj_part;
}

Bonus:

most people get confused with the j>=i constraint. If you have a feeling for numbers, you should be able to see that i should tend to be lower than j.

Assume we have our formula, it is maximized and i > j. (this is impossible, but lets check it out) we define x1 := j-i and x2 = i-j

A[i]+A[j]+j-i = A[i]+A[j] + x1, x1 < 0

we could then swap i with j and end up with this:

A[j]+A[i]+i-j = A[i]+A[j] + x2, x2 > 0

it is basically the same formula, but now because i > j the second formula will be greater than the first. In other words we could increase the maximum by swapping i and j which can't be true if we already had the maximum. If we ever find a maximum, i cannot be greater than j.