Last Updated: 4 Mar, 2021

Maximum value of modulus expression

Moderate

Asked in companies

Solve now

Problem statement

You are given two arrays ‘ARR1’ and ‘ARR2’ having equal length ‘N’. Your task is to return the maximum value of the expression:

|ARR1[ i ] - ARR1[ j ]| + |ARR2[ i ] - ARR2[ j ]| + |i - j|, where 0 <= i, j < n and ‘|A|’ represents the absolute (i.e., non-negative) value of ‘A’.

Example:

n = 4, ARR1 = {1, 2, 3, 4}, ARR2 = {-1, 3, 4, 2}

The maximum value of the expression is obtained when indexes ‘i = 0’ and ‘j = 3’. After  evaluating the expression, we get: 
|ARR1[0] - ARR2[3]| + |ARR2[0] - ARR2[3]| + |0 - 3| => |1 - 4| + |-1 - 2| + |-3| => |-3| + |-3| + 3 => 9

So the answer is 9.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the length of array ‘ARR1’ and ‘ARR2’.

The second line of each test case contains 'N' space-separated integers denoting the elements of array 'ARR1'.

The third line of each test case contains 'N' space-separated integers denoting the elements of array 'ARR2'.

Output format:

For each test case, print a single line containing a single integer denoting the maximum value of the given expression.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 1000
-10 ^ 6 <= ARR1[ i ], ARR2[ i ] <= 10 ^ 6

Where ‘T’ is the total number of test cases, ‘N’ denotes the length of arrays 'ARR1' & 'ARR2',  and ‘ARR1[i]’ & ‘ARR2[i]’ represents the elements in the respective arrays

Time limit: 1 sec.

Solve now

Approaches

01 Approach

We can use two nested loops to iterate through all the possible ‘N * N’ pairs of indexes ‘i’ and ‘j’ to obtain the given expression’s maximum value.

Initialize variable ‘MAXEXP = INT_MIN’ and use it to store the final answer. ‘INT_MIN’ is the minimum integer value. Use variable ‘CUREXP’ to store the value of the expression in the current iteration.
Run a loop where ‘i’ ranges from ‘0’ to ‘n-1’.
- Run a loop where ‘j’ ranges from ‘0’ to ‘n-1’.
  - Compute ‘CUREXP = abs(ARR1[i] - ARR1[j]) + abs(ARR2[i] - ARR2[j]) + abs(i - j)’. The ‘abs’ function returns the absolute value of given integer.
  - If ‘MAXEXP’ is less than ‘CUREXP’ then ‘MAXEXP = CUREXP’.
Return ‘MAXEXP’ as the answer.

Solve now

02 Approach

Consider the following properties of the modulus function:

|A| = max(-A, A).
|A| + |B| = max(A + B, A - B, -A + B, -A - B).
|A| + |B| + |C| = max(A + B + C, A - B + C, -A + B + C, -A - B + C, A + B - C, A - B - C, -A + B - C, -A - B - C).

The expression given in the problem is similar to the third equation, after replacing ‘A = ARR1[i] - ARR2[j]’, ‘B = ARR2[i] - ARR2[j]’ and ‘C = i - j’ the given expression can be written as maximum of the following 8 expressions:

In the above expressions, the terms in both brackets are the same. We discuss how to solve equation 1 below. Similarly, we can also solve the remaining equations

We need to find the maximum of equation 1. Let’s construct an imaginary array ‘X’ of size ‘n’ and where ‘X[i] = ARR1[i] + ARR2[i] + i’. So, equation 1 can be reduced to ‘max(X[i]) - min(X[i])’. Instead of creating an array ‘X’, we can use two variables, ‘maxVal1’ and ‘MINVAL1’, to store the maximum and minimum value of the expression in ‘X[i]’. Equations 1 and 8 are virtually the same because the array ‘X’ generated for both the equations is the same.

Similarly, equations 2&7, 3&6, and 4&5 are virtually the same. So, the given problem’s expression reduces to finding ‘maximum of equation (1, 2, 3, 4)’. Following are the steps to solve the problem:

Initialize variables, ‘MAXVAL1= INT_MAX’, ‘MINVAL1= INT_MIN’, ‘MAXVAL2= INT_MAX’, ‘MINVAL2= INT_MIN’, ‘MAXVAL3= INT_MAX’, ‘MINVAL3= INT_MIN’, ‘MAXVAL4= INT_MAX’, ‘MINVAL4= INT_MIN’. Use ‘maxVal’ and ‘minVal’ to store the max and min values of the respective equations. ‘INT_MAX’ is the maximum and ‘INT_MIN’ is the minimum integer value.
Run a loop where ‘i’ ranges from 0 to ‘n-1’.
- For equation 1,
  - ‘MAXVAL1 = max( ARR1[i] + ARR2[i] + i, MAXVAL1)’
  - ‘MINVAL1= min( ARR1[i] + ARR2[i] + i, MINVAL1)’
- For equation 2,
  - ‘MAXVAL2 = max( ARR1[i] - ARR2[i] + i, MAXVAL2)’
  - ‘MINVAL2 = min( ARR1[i] - ARR2[i] + i, MINVAL2)’
- For equation 3,
  - ‘MAXVAL3 = max( ARR1[i] - ARR2[i] - i, MAXVAL3)’
  - ‘MINVAL3 = min( ARR1[i] - ARR2[i] - i, MINVAL3)’
- For equation 4,
  - ‘MAXVAL4 = max( ARR1[i] + ARR2[i] - i, MAXVAL4)’
  - ‘MINVAL4 = min( ARR1[i] + ARR2[i] - i, MINVAL4)’
- The functions ‘max’ and ‘min’ return the largest, and the smallest value among the values passed to them, respectively.
Create a variable ‘ans’ to store the answer.
‘ans = max(MAXVAL1 - MINVAL1 , MAXVAL2 - MINVAL2, MAXVAL3 - MINVAL3, MAXVAL4 - MINVAL4)’
Return ‘ANS’ as the answer.

Solve now