Find which two values ​​in the array maximize the given expression?

Question

I met a very simple question, but my solution is wrong. Any help on this? 1) any errors in my decision? 2) any good idea for O (n) time complexity?

Question:

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

My decision:

 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]+(ji); if(cur_dis > max_dis) max_dis=cur_dis; } } return max_dis; } 

Answer 1

The crucial understanding is that this can be done in O (n) only if you keep track of where the potentially useful values ​​are before you make sure they become usable.

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

Let me call the X value for some values ​​of i and j "X _{i, j} " and start by writing our best solution so far ala X _best = X <sub> 0,0sub>

The increment n along the array ...

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

• when using n , since the index "j" gives X _{max_i, n is} greater than X _best , best_i = max_i, best_j = n.

Discussion - why / how it works

j_random_hacker comment offers me a sketch of the proof, but honestly I don’t know where to start. I will try to explain as much as possible - if anyone has a better explanation, please chip ....

Repeating the problem: the largest X _{i, j} , where j> = i. Given that we can set the initial X _best X _0.0 , the problem is to know when to update it and why. Since we consider sequential indices in the array as potential values ​​for j, we want to generate X _{i, j = n} for some i (discussed later) for comparison with X _best , but what do I value for use? Well, if any index from 0 to n is <= j, the restriction j> = i does not matter if we choose the best value i from the indexes we have already visited. We proceed from the best value of i, separating the i-related contribution to X from the j-related contribution - A[i] - i - therefore, in preparation for considering whether we have a new best solution with j = n, we must support the variable best_i too when we go.

The way to solve the problem

Whatever it costs - when I was groping for a solution, I wrote down on paper some imaginary contributions i and j that I could see, covering interesting cases ... where Ci and Cj are the contributions associated with using n like me and j, respectively sort of

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

You will notice that I did not choose the values ​​where Ci could be A [i] - i, and Cj could be A [j] + j ... I could see that the resulting solution should work for any formulas, and that just made it difficult to capture interesting cases. So, what is an interesting case? When n = 2, the value of Ci is higher than everything that we saw in the earlier elements, but, given only the knowledge of these early elements, we still do not see a way to use it. This scenario is the only "big" complication of the problem. Why do we need a Cj value of at least 9, so Xbest improves, which happens when n = 4. If we found an even better Ci in [3], then of course we would like to use it. best_i, where this waiting expectation index is good enough - Cj.

Answer 2

A longer version of my comment: how about iterating the array from both ends, trying to find the largest number, reducing it at a distance from the end of the appripriate. Will they find the correct indexes (and therefore 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] + ji); 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 will write in pseudocode because I have little time, but this should be the most efficient 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 you just call

 compare(array,0,array.length); 

I think I found an incredibly quick solution, but you need to check it out:

you need to rewrite your array as follows

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

Then you just find the 2 highest values ​​of the array and sum them up, this should be your solution, almost O (n)

wait, maybe something is missing for me ... I have to check.

Ok, you get the 2 highest values ​​from this new array and keep the positions of i and j. Then you need to calculate your result from the source array.

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

This should be the implementation of the method proposed by Tony D. (in C #), which 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;