O(n) C++ Solution

int Solution::maxArr(vector &A) {
int curr_max = A[0];
int curr_min = A[0];
int curr_max_idx = 0;
int curr_min_idx = 0;
int difference = 0;
int diff = 0;
//#define DEBUG

for (auto i = 1; i < A.size(); i++) {
    
    if (A[i] >= curr_max) {
        curr_max = A[i];
        curr_max_idx = i;
    }
    else if (A[i] <= curr_min) {
        curr_min = A[i];
        curr_min_idx = i;
    }
    
    diff = abs(curr_max - curr_min) + abs(curr_max_idx - curr_min_idx);
    #ifdef DEBUG
    cout << "diff " << diff << " max val " << curr_max << " min val " << curr_min 
    << " max idx " << curr_max_idx << " min idx " << curr_min_idx << endl;
    #endif
    if (diff >= difference) {
        difference = diff;
    }
}

return difference;

}

For the example
A : [ 55, -8, 43, 52, 8, 59, -91, -79, -18, -94 ]
Max = 59 Index = 6
Min = -94 Index = 10
f(i,j) = f(6,10) = |59-(-94)| + |6-10| = 153 + 4 = 157
Which is the output my program also gives.
However my submission fails as expected answer is 158
Which I am not sure if is correct.
Nevertheless, I believe I have a pretty functional O(n) solution

Your code is giving wrong answer . If you do the calculation for first and last entry you will find that 158 is indeed the correct answer. I’m also not sure how to solve this problem by iterative method.

Click here to start solving coding interview questions