Maximum value of modulus expression
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 |-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

Question

Maximum value of modulus expression

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.

Accepted Answer

Brute force

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space, space complexity is constant.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the array’s size.

The outer loop and the inner loop both run 'N' times, so the total number of iterations is ‘N * N’.

Java (SE 1.8)

/*

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    where N is the array's size.

*/



import java.util.ArrayList;



public class Solution {

	public static int maxValueOfModulusExpression(ArrayList arr1, ArrayList arr2, int n) {



		// Smallest possible value.

		int maxExp = Integer.MIN_VALUE;



		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n; j++) {

				maxExp = Math.max(maxExp,

						Math.abs(arr1.get(i) - arr1.get(j)) + Math.abs(arr2.get(i) - arr2.get(j)) + Math.abs(i - j));

			}

		}

    

		return maxExp;

	}

}

Python (3.5)

'''

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    where N is the array's size.   

'''



def maxValueOfModulusExpression(arr1, arr2, n):



    # 'float("-inf")': Smallest possible value of integer.

    maxExp = float("-inf")



    for i in range(n):

        for j in range(n):

            maxExp = max(maxExp, abs(

                arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j))



    return maxExp

C++ (g++ 5.4)

/*

    Time Complexity : O(N ^ 2)

    Space Complexity : O(1)



    where N is the array's size.

*/



int maxValueOfModulusExpression(vector& arr1, vector& arr2, int n) 

{

    // Smallest possible value.

    int maxExp = INT32_MIN;  

        

    for (int i = 0; i < n; i++) 

    {

        for (int j = 0; j < n; j++) 

        {

            maxExp = max(maxExp, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j));

        }

    }

    

    return maxExp;

}

Accepted Answer

Expand the modulus function

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.