Home Express Maximize the Absolute Value of Expression |arr1[i] – arr1[j]| + |arr2[i] – arr2[j]| + |i – j|

Maximize the Absolute Value of Expression |arr1[i] – arr1[j]| + |arr2[i] – arr2[j]| + |i – j|

Maximize Array sum except elements from [i, i+X] for all i such that arr[i] > K

Find the Sum of Mutated Array Closest to Target

Given two integer arrays arr1[] and arr2[] of equal length, the task is to find the maximum value of the expression: |arr1[i] – arr1[j]| + |arr2[i] – arr2[j]| + |i – j|, where the maximum is taken over all valid indices i and j satisfying 0 <= i, j < arr1.length. Return the maximum value of the expression.

Example:

Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
Output: 13

Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
Output: 20

Approach:

We can solve this problem by extracting the equation and put things in order:

Suppose i >= j :

| arr1[i] – arr2[i] | + | arr1[j] – arr2[j] | + | i-j |

Turn into :

  • Case 1: arr1[i] > arr2[i] and arr1[j] > arr2[j]
    • [ – ( arr1[j] + arr2[j] ) -j ] + [ ( arr1[i] + arr2[i] ) + i ]
  • Case 2: arr1[i] < arr2[i] and arr1[j] < arr2[j]
    • [ ( arr1[j] + arr2[j] ) – j ] + [- ( arr1[i] + arr2[i] ) + i]
  • Case 3: arr1[i] > arr2[i] and arr1[j] < arr2[j]
    • [ – ( arr1[j] – arr2[j] ) – j ] + [ ( arr1[i] – arr2[i] ) + i ]
  • Case 4: arr1[i] < arr2[i] and arr1[i] > arr2[[j]
    • [( arr1[j] – arr2[j] ) – j ] + [- ( arr1[i] – arr2[i] ) + i]

In every case, we have the pattern: A+B
Now, the result is maxB – minA. Our job is to loop through all cases of each element and update A and B.

Steps-by-step approach:

  • Calculate Expressions:
    • Create a new array arr3 by applying signs (+/-) to arr1 and arr2 elements and adding their indices for all four sign combinations.
  • Find Maximum Difference:
    • For each combination (arr3):
      • Find the maximum difference between any element in arr3 and the current minimum value seen so far.
  • Overall Maximum:
    • Compare the maximum differences obtained from each combination. The largest difference is the final answer.
  • Using the Input:
    • Calculate arr3 for (+,+), (+,-), (-,+), and (-,-) combinations.
    • For each arr3:
      • Find the difference between elements and the running minimum within that arr3.
      • Keep track of the largest difference found across all arr3.
  • The final answer is the maximum difference found across all combinations.

Below is the implementation of the above approach:

C++ 
#include <iostream>
#include <vector>

using namespace std;

// Helper function to calculate the maximum absolute
// value expression for a specific combination of signs
int helper(int sign1, int sign2, vector<int>& arr1,
           vector<int>& arr2)
{
    int n = arr1.size();
    vector<int> arr3(n, 0);

    // Create a new array (arr3) by applying signs
    // (sign1, sign2) to elements of arr1, arr2, and
    // adding their indices
    for (int i = 0; i < n; ++i) {
        arr3[i] = sign1 * arr1[i] + sign2 * arr2[i] + i;
    }

    int res = 0;
    int minVal = arr3[0];

    // Find the maximum difference between any element
    // (arr3[i]) and the minimum value seen so far
    // (minVal)
    for (int i = 1; i < n; ++i) {
        res = max(res, arr3[i] - minVal);
        minVal = min(minVal, arr3[i]);
    }

    return res;
}

// Main function to find the maximum absolute value
// expression for all possible sign combinations
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2)
{
    int res = 0;

    // Call the helper function with all four sign
    // combinations (+, +), (+, -), (-, +), (-, -)
    res = max(res, helper(1, 1, arr1, arr2));
    res = max(res, helper(1, -1, arr1, arr2));
    res = max(res, helper(-1, 1, arr1, arr2));
    res = max(res, helper(-1, -1, arr1, arr2));

    return res;
}

int main()
{
    // Given input arrays
    vector<int> arr1 = { 1, 2, 3, 4 };
    vector<int> arr2 = { -1, 4, 5, 6 };

    int max_value = maxAbsValExpr(arr1, arr2);

    cout << "The maximum absolute value expression is: "
         << max_value << endl;

    return 0;
}
Java 
import java.util.*;

public class Main {

    // Helper function to calculate the maximum absolute value expression for a specific combination of signs
    public static int helper(int sign1, int sign2, List<Integer> arr1, List<Integer> arr2) {
        int n = arr1.size();
        List<Integer> arr3 = new ArrayList<>(Collections.nCopies(n, 0));

        // Create a new array (arr3) by applying signs (sign1, sign2) to elements of arr1, arr2, and adding their indices
        for (int i = 0; i < n; ++i) {
            arr3.set(i, sign1 * arr1.get(i) + sign2 * arr2.get(i) + i);
        }

        int res = 0;
        int minVal = arr3.get(0);

        // Find the maximum difference between any element (arr3[i]) and the minimum value seen so far (minVal)
        for (int i = 1; i < n; ++i) {
            res = Math.max(res, arr3.get(i) - minVal);
            minVal = Math.min(minVal, arr3.get(i));
        }

        return res;
    }

    // Main function to find the maximum absolute value expression for all possible sign combinations
    public static int maxAbsValExpr(List<Integer> arr1, List<Integer> arr2) {
        int res = 0;

        // Call the helper function with all four sign combinations (+, +), (+, -), (-, +), (-, -)
        res = Math.max(res, helper(1, 1, arr1, arr2));
        res = Math.max(res, helper(1, -1, arr1, arr2));
        res = Math.max(res, helper(-1, 1, arr1, arr2));
        res = Math.max(res, helper(-1, -1, arr1, arr2));

        return res;
    }

    public static void main(String[] args) {
        // Given input arrays
        List<Integer> arr1 = Arrays.asList(1, 2, 3, 4);
        List<Integer> arr2 = Arrays.asList(-1, 4, 5, 6);

        int maxValue = maxAbsValExpr(arr1, arr2);

        System.out.println("The maximum absolute value expression is: " + maxValue);
    }
}


// This code is contributed by Shivam Gupta
Python 
# Helper function to calculate the maximum absolute
# value expression for a specific combination of signs
def helper(sign1, sign2, arr1, arr2):
    n = len(arr1)
    arr3 = [0] * n

    # Create a new array (arr3) by applying signs
    # (sign1, sign2) to elements of arr1, arr2, and
    # adding their indices
    for i in range(n):
        arr3[i] = sign1 * arr1[i] + sign2 * arr2[i] + i

    res = 0
    minVal = arr3[0]

    # Find the maximum difference between any element
    # (arr3[i]) and the minimum value seen so far
    # (minVal)
    for i in range(1, n):
        res = max(res, arr3[i] - minVal)
        minVal = min(minVal, arr3[i])

    return res

# Main function to find the maximum absolute value
# expression for all possible sign combinations
def maxAbsValExpr(arr1, arr2):
    res = 0

    # Call the helper function with all four sign
    # combinations (+, +), (+, -), (-, +), (-, -)
    res = max(res, helper(1, 1, arr1, arr2))
    res = max(res, helper(1, -1, arr1, arr2))
    res = max(res, helper(-1, 1, arr1, arr2))
    res = max(res, helper(-1, -1, arr1, arr2))

    return res

# Given input arrays
arr1 = [1, 2, 3, 4]
arr2 = [-1, 4, 5, 6]

max_value = maxAbsValExpr(arr1, arr2)

print("The maximum absolute value expression is:", max_value)

# This code is contributed by Shivam Gupta
JavaScript 
// Helper function to calculate the maximum absolute
// value expression for a specific combination of signs
function helper(sign1, sign2, arr1, arr2) {
    const n = arr1.length;
    const arr3 = new Array(n).fill(0);

    // Create a new array (arr3) by applying signs
    // (sign1, sign2) to elements of arr1, arr2, and
    // adding their indices
    for (let i = 0; i < n; ++i) {
        arr3[i] = sign1 * arr1[i] + sign2 * arr2[i] + i;
    }

    let res = 0;
    let minVal = arr3[0];

    // Find the maximum difference between any element
    // (arr3[i]) and the minimum value seen so far
    // (minVal)
    for (let i = 1; i < n; ++i) {
        res = Math.max(res, arr3[i] - minVal);
        minVal = Math.min(minVal, arr3[i]);
    }

    return res;
}

// Main function to find the maximum absolute value
// expression for all possible sign combinations
function maxAbsValExpr(arr1, arr2) {
    let res = 0;

    // Call the helper function with all four sign
    // combinations (+, +), (+, -), (-, +), (-, -)
    res = Math.max(res, helper(1, 1, arr1, arr2));
    res = Math.max(res, helper(1, -1, arr1, arr2));
    res = Math.max(res, helper(-1, 1, arr1, arr2));
    res = Math.max(res, helper(-1, -1, arr1, arr2));

    return res;
}

// Example usage
const arr1 = [1, 2, 3, 4];
const arr2 = [-1, 4, 5, 6];

const max_value = maxAbsValExpr(arr1, arr2);

console.log(`The maximum absolute value expression is: ${max_value}`);
// This code is contributed by Yash Agarwal

Output
The maximum absolute value expression is: 13

Time complexity: O(N)
Auxiliary Space: O(N)




Tags:
#Microsoft #Arrays #DSA #Microsoft #Arrays

Maximize Array sum except elements from [i, i+X] for all i such that arr[i] > K

Find the Sum of Mutated Array Closest to Target

Contact Us

Categories
Learn the most popular programming languages in the world.