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

first we can easily solve using two for loops
then we can optimize by removing mod operations, doing simple maths

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.