Unsure if given solution is correct

For the sample input [ 55, -8, 43, 52, 8, 59, -91, -79, -18, -94 ] the expected value = 158. But I believe the answer should be 157.

I used Ruby to solve this problem and I keep getting 157 for the output, and it makes sense when I use the formula for f(i, j).

For the inputs above, the max value is 59 and index 5, and the min value is -94 at index 9.

The formula we are given is f(i,j) = |A[i] - A[j] | + |[i - j]|

When plugging in the values above for the formula we get:

f(5, 9) = |A[5] - A[9]| + |5 - 9|
= |59 - (-94)| + |-4|
= 153 + 4 = 157

What am I doing wrong that is giving me an off by 1 error?

you will get 158 as max result
take 55 (index 0) and -94 (index 9):
|55-(-94)| + |0-9|=149+9=158
hence 158 is correct answer.
you don’t have to find max and min value,you have to maximize the function.

Hey akul-gupta,

Thank you for your response. I thought we couldn’t use 0 as a value though? The problem states:

maximum value of f(i, j) for all 1 ≤ i, j ≤ N

Look carefully, problem statement assumes indexing is one based (1 to n instead of 0 to n-1). According to that index of 55 will be 1 while index of -94 will be 10. But still,

|55 - (-94)| + |1 - 10| = 149 + 9 = 158.

Since difference of indexes has been taken here |i - j|, no matter which indexing (0 based or 1 based) we use, we’ll end up with same answer. Cause -

|i - j| = |(i - 1) - (j - 1)|

Hope it helps!!

Click here to start solving coding interview questions