Maximum value of modulus expression

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in companies
DelhiveryPayPalAlgo8

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample input 1:

2
4
4 3 2 5
5 -5 1 1
4
-2 -3 3 2
4 4 4 0

Sample output 1:

12
11

Explanation of sample input 1:

Test Case 1:

The maximum value of the expression is obtained when indexes ‘i = 0’ and ‘j = 1’. After  evaluating the expression, we get: 
|ARR1[0] - ARR2[1]| + |ARR2[0] - ARR2[1]| + |0 - 1| => |4 - 3| + |5 - (-5)| + |-1| => |1| + |10| + 1 => 12
So the answer is 12.

Test Case 2:

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

Sample input 2:

2
5
1 -2 -3 4 5
-5 -4 -3 2 1
3
10 -1 12
8 0 5

Sample output 2:

15
20
Hint

Evaluate the given expression over all the possible pairs of ‘i’ and ‘j’.

Approaches (2)
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.
Time Complexity

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’.

Space Complexity

O(1).

 

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

Code Solution
(100% EXP penalty)
Maximum value of modulus expression
Full screen
Console