Valor máximo de |arr[i] – arr[j]| + |i – j|

Dada una array de N enteros positivos. La tarea es encontrar el valor máximo de |arr[i] – arr[j]| + |i – j|, donde 0 <= i, j <= N – 1 y arr[i], arr[j] pertenecen al arreglo.

Ejemplos: 

Entrada: N = 4, arr[] = { 1, 2, 3, 1 } 
Salida: 4
Explicación:
Elija i = 0 y j = 2. Esto dará como resultado |1-3|+|0-2| = 4 que es el valor máximo posible.

Entrada: N = 3, arr[] = { 1, 1, 1 }
Salida: 2

Método 1: La idea es usar la fuerza bruta, es decir, iterar en dos bucles for.

A continuación se muestra la implementación de este enfoque:  

#include <bits/stdc++.h>
using namespace std;
#define MAX 10
 
// Return maximum value of |arr[i] - arr[j]| + |i - j|
int findValue(int arr[], int n)
{
    int ans = 0;
 
    // Iterating two for loop, one for
    // i and another for j.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
 
            // Evaluating |arr[i] - arr[j]| + |i - j|
            // and compare with previous maximum.
            ans = max(ans,
                      abs(arr[i] - arr[j]) + abs(i - j));
 
    return ans;
}
 
// Driven Program
int main()
{
    int arr[] = { 1, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findValue(arr, n) << endl;
 
    return 0;
}

// java program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
class GFG {
    static final int MAX = 10;
 
    // Return maximum value of
    // |arr[i] - arr[j]| + |i - j|
    static int findValue(int arr[], int n)
    {
        int ans = 0;
 
        // Iterating two for loop,
        // one for i and another for j.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
 
                // Evaluating |arr[i] - arr[j]|
                // + |i - j| and compare with
                // previous maximum.
                ans = Math.max(ans,
                               Math.abs(arr[i] - arr[j])
                               + Math.abs(i - j));
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 1 };
        int n = arr.length;
 
        System.out.println(findValue(arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find
# maximum value of
# |arr[i] - arr[j]| + |i - j|
 
# Return maximum value of
# |arr[i] - arr[j]| + |i - j|
def findValue(arr, n):
    ans = 0;
     
    # Iterating two for loop,
    # one for i and another for j.
    for i in range(n):
        for j in range(n):
             
            # Evaluating |arr[i] -
            # arr[j]| + |i - j|
            # and compare with
            # previous maximum.
            ans = ans if ans>(abs(arr[i] - arr[j]) +
                              abs(i - j)) else (abs(arr[i] -
                                      arr[j]) + abs(i - j)) ;
    return ans;
     
# Driver Code
arr = [1, 2, 3, 1];
n = len(arr);
print(findValue(arr, n));
 
# This code is contributed by mits.

// C# program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
using System;
 
class GFG {
     
    // Return maximum value of
    // |arr[i] - arr[j]| + |i - j|
    static int findValue(int []arr, int n)
    {
        int ans = 0;
     
        // Iterating two for loop,
        // one for i and another for j.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
     
                // Evaluating |arr[i] - arr[j]|
                // + |i - j| and compare with
                // previous maximum.
                ans = Math.Max(ans,
                    Math.Abs(arr[i] - arr[j])
                            + Math.Abs(i - j));
     
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 1, 2, 3, 1 };
        int n =arr.Length;
         
        Console.Write(findValue(arr, n));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
$MAX = 10;
 
// Return maximum value of
// |arr[i] - arr[j]| + |i - j|
function findValue($arr, $n)
{
    $ans = 0;
 
    // Iterating two for loop,
    // one for i and another for j.
    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $n; $j++)
 
            // Evaluating |arr[i] -
            // arr[j]| + |i - j|
            // and compare with
            // previous maximum.
            $ans = max($ans, abs($arr[$i] -
                   $arr[$j]) + abs($i - $j));
 
    return $ans;
}
     
    // Driver Code
    $arr = array(1, 2, 3, 1);
    $n = count($arr);
 
    echo findValue($arr, $n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
var MAX = 10;
 
// Return maximum value of
// |arr[i] - arr[j]| + |i - j|
function findValue(arr , n)
{
    var ans = 0;
 
    // Iterating two for loop,
    // one for i and another for j.
    for(var i = 0; i < n; i++)
        for(var j = 0; j < n; j++)
 
            // Evaluating |arr[i] - arr[j]|
            // + |i - j| and compare with
            // previous maximum.
            ans = Math.max(ans,
                           Math.abs(arr[i] - arr[j]) +
                           Math.abs(i - j));
                            
    return ans;
}
 
// Driver code
var arr = [ 1, 2, 3, 1 ];
var n = arr.length;
 
document.write(findValue(arr, n));
 
// This code is contributed by shikhasingrajput
 
</script>

4

Método 2 (complicado): En primer lugar, hagamos cuatro ecuaciones eliminando los signos de valor absoluto («|»). Se formarán las siguientes 4 ecuaciones, y necesitamos encontrar el valor máximo de estas ecuaciones y esa será nuestra respuesta. 

1. arr[i] – arr[j] + i – j = (arr[i] + i) – (arr[j] + j)
2. arr[i] – arr[j] – i + j = (arr[i] – i) – (arr[j] – j)
3. -arr[i] + arr[j] + i – j = -(arr[i] – i) + (arr[j] – j)
4. -arr[i] + arr[j] – i + j = -(arr[i] + i) + (arr[j] + j)

Observe que las ecuaciones (1) y (4) son idénticas. De manera similar, las ecuaciones (2) y (3) son idénticas.
Ahora la tarea es encontrar el valor máximo de estas ecuaciones. Entonces, el enfoque es formar dos arrays, first_array[], almacenará arr[i] + i, 0 <= i < n, second_array[], almacenará arr[i] – i, 0 <= i < n . 
Ahora nuestra tarea es fácil, solo necesitamos encontrar la diferencia máxima entre los dos valores de estas dos arrays.
Para eso, encontramos el valor máximo y el valor mínimo en el primer_arreglo y almacenamos su diferencia: 
ans1 = (valor máximo en el primer_arreglo – valor mínimo en el primer_arreglo) 
De manera similar, necesitamos encontrar el valor máximo y el valor mínimo en el segundo_arreglo y almacenar sus diferencia: 
ans2 = (valor máximo en second_array – valor mínimo en second_array) 
Nuestra respuesta será un máximo de ans1 y ans2.

A continuación se muestra la implementación del enfoque anterior: 

// Efficient CPP program to find maximum value
// of |arr[i] - arr[j]| + |i - j|
#include <bits/stdc++.h>
using namespace std;
 
// Return maximum |arr[i] - arr[j]| + |i - j|
int findValue(int arr[], int n)
{
    int a[n], b[n], tmp;
 
    // Calculating first_array and second_array
    for (int i = 0; i < n; i++)
    {
        a[i] = (arr[i] + i);
        b[i] = (arr[i] - i);
    }
 
    int x = a[0], y = a[0];
 
    // Finding maximum and minimum value in
    // first_array
    for (int i = 0; i < n; i++)
    {
        if (a[i] > x)
            x = a[i];
 
        if (a[i] < y)
            y = a[i];
    }
 
    // Storing the difference between maximum and
    // minimum value in first_array
    int ans1 = (x - y);
 
    x = b[0];
    y = b[0];
 
    // Finding maximum and minimum value in
    // second_array
    for (int i = 0; i < n; i++)
    {
        if (b[i] > x)
            x = b[i];
 
        if (b[i] < y)
            y = b[i];
    }
 
    // Storing the difference between maximum and
    // minimum value in second_array
    int ans2 = (x - y);
 
    return max(ans1, ans2);
}
 
// Driven Code
int main()
{
    int arr[] = { 1, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findValue(arr, n) << endl;
 
    return 0;
}

// Efficient Java program to find maximum
// value of |arr[i] - arr[j]| + |i - j|
import java.io.*;
class GFG {
 
    // Return maximum |arr[i] -
    // arr[j]| + |i - j|
    static int findValue(int arr[], int n)
    {
        int a[] = new int[n];
        int b[] = new int[n];
        int tmp;
 
        // Calculating first_array
        // and second_array
        for (int i = 0; i < n; i++)
        {
            a[i] = (arr[i] + i);
            b[i] = (arr[i] - i);
        }
 
        int x = a[0], y = a[0];
 
        // Finding maximum and
        // minimum value in
        // first_array
        for (int i = 0; i < n; i++)
        {
            if (a[i] > x)
                x = a[i];
 
            if (a[i] < y)
                y = a[i];
        }
 
        // Storing the difference
        // between maximum and
        // minimum value in first_array
        int ans1 = (x - y);
 
        x = b[0];
        y = b[0];
 
        // Finding maximum and
        // minimum value in
        // second_array
        for (int i = 0; i < n; i++)
        {
            if (b[i] > x)
                x = b[i];
 
            if (b[i] < y)
                y = b[i];
        }
 
        // Storing the difference
        // between maximum and
        // minimum value in second_array
        int ans2 = (x - y);
 
        return Math.max(ans1, ans2);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 1 };
        int n = arr.length;
        System.out.println(findValue(arr, n));
    }
}
 
// This code is contributed by anuj_67.

# Efficient Python3 program
# to find maximum value
# of |arr[i] - arr[j]| + |i - j|
 
# Return maximum |arr[i] -
# arr[j]| + |i - j|
 
 
def findValue(arr, n):
    a = []
    b = []
 
    # Calculating first_array
    # and second_array
    for i in range(n):
        a.append(arr[i] + i)
        b.append(arr[i] - i)
 
    x = a[0]
    y = a[0]
 
    # Finding maximum and
    # minimum value in
    # first_array
    for i in range(n):
        if (a[i] > x):
            x = a[i]
 
        if (a[i] < y):
            y = a[i]
 
    # Storing the difference
    # between maximum and
    # minimum value in first_array
    ans1 = (x - y)
 
    x = b[0]
    y = b[0]
 
    # Finding maximum and
    # minimum value in
    # second_array
    for i in range(n):
        if (b[i] > x):
            x = b[i]
 
        if (b[i] < y):
            y = b[i]
 
    # Storing the difference
    # between maximum and
    # minimum value in
    # second_array
    ans2 = (x - y)
 
    return max(ans1, ans2)
 
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 1]
    n = len(arr)
 
    print(findValue(arr, n))
 
# This code is contributed by mits

// Efficient Java program to find maximum
// value of |arr[i] - arr[j]| + |i - j|
using System;
class GFG {
 
    // Return maximum |arr[i] -
    // arr[j]| + |i - j|
    static int findValue(int[] arr, int n)
    {
        int[] a = new int[n];
        int[] b = new int[n];
        // int tmp;
 
        // Calculating first_array
        // and second_array
        for (int i = 0; i < n; i++)
        {
            a[i] = (arr[i] + i);
            b[i] = (arr[i] - i);
        }
 
        int x = a[0], y = a[0];
 
        // Finding maximum and
        // minimum value in
        // first_array
        for (int i = 0; i < n; i++)
        {
            if (a[i] > x)
                x = a[i];
 
            if (a[i] < y)
                y = a[i];
        }
 
        // Storing the difference
        // between maximum and
        // minimum value in first_array
        int ans1 = (x - y);
 
        x = b[0];
        y = b[0];
 
        // Finding maximum and
        // minimum value in
        // second_array
        for (int i = 0; i < n; i++)
        {
            if (b[i] > x)
                x = b[i];
 
            if (b[i] < y)
                y = b[i];
        }
 
        // Storing the difference
        // between maximum and
        // minimum value in second_array
        int ans2 = (x - y);
 
        return Math.Max(ans1, ans2);
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 1 };
        int n = arr.Length;
        Console.WriteLine(findValue(arr, n));
    }
}
 
// This code is contributed by anuj_67.

<?php
// Efficient CPP program
// to find maximum value
// of |arr[i] - arr[j]| + |i - j|
 
// Return maximum |arr[i] -
// arr[j]| + |i - j|
function findValue($arr, $n)
{
    $a[] =array(); $b=array();$tmp;
 
    // Calculating first_array
    // and second_array
    for ($i = 0; $i < $n; $i++)
    {
        $a[$i] = ($arr[$i] + $i);
        $b[$i] = ($arr[$i] - $i);
    }
 
    $x = $a[0]; $y = $a[0];
 
    // Finding maximum and
    // minimum value in
    // first_array
    for ($i = 0; $i < $n; $i++)
    {
        if ($a[$i] > $x)
        $x = $a[$i];
 
        if ($a[$i] < $y)
            $y = $a[$i];
    }
 
    // Storing the difference
    // between maximum and
    // minimum value in first_array
    $ans1 = ($x - $y);
 
    $x = $b[0];
    $y = $b[0];
 
    // Finding maximum and
    // minimum value in
    // second_array
    for ($i = 0; $i < $n; $i++)
    {
        if ($b[$i] > $x)
            $x = $b[$i];
 
        if ($b[$i] < $y)
            $y = $b[$i];
    }
 
    // Storing the difference
    // between maximum and
    // minimum value in
    // second_array
    $ans2 = ($x -$y);
 
    return max($ans1, $ans2);
}
 
    // Driver Code
    $arr = array(1, 2, 3, 1);
    $n = count($arr);
 
    echo findValue($arr, $n);
     
// This code is contributed by anuj_67.
?>

<script>
    // Efficient Javascript program to find maximum
    // value of |arr[i] - arr[j]| + |i - j|
     
    // Return maximum |arr[i] -
    // arr[j]| + |i - j|
    function findValue(arr, n)
    {
        let a = new Array(n);
        let b = new Array(n);
        // int tmp;
  
        // Calculating first_array
        // and second_array
        for (let i = 0; i < n; i++)
        {
            a[i] = (arr[i] + i);
            b[i] = (arr[i] - i);
        }
  
        let x = a[0], y = a[0];
  
        // Finding maximum and
        // minimum value in
        // first_array
        for (let i = 0; i < n; i++)
        {
            if (a[i] > x)
                x = a[i];
  
            if (a[i] < y)
                y = a[i];
        }
  
        // Storing the difference
        // between maximum and
        // minimum value in first_array
        let ans1 = (x - y);
  
        x = b[0];
        y = b[0];
  
        // Finding maximum and
        // minimum value in
        // second_array
        for (let i = 0; i < n; i++)
        {
            if (b[i] > x)
                x = b[i];
  
            if (b[i] < y)
                y = b[i];
        }
  
        // Storing the difference
        // between maximum and
        // minimum value in second_array
        let ans2 = (x - y);
  
        return Math.max(ans1, ans2);
    }
     
    let arr = [ 1, 2, 3, 1 ];
    let n = arr.length;
    document.write(findValue(arr, n));
     
</script>

4

Método – 3

This solution is space optimization on above mentioned (method2) solution.
In Method 2 solution we had used two matrix of size n which laid to O(n) space complexity 
but here we only use O(1) space instead of that two n size array

Implementación:

// Optimized CPP program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
#include <bits/stdc++.h>
using namespace std;
 
// Return maximum |arr[i] - arr[j]| + |i - j|
int findValue(int arr[], int n)
{
    int temp1, temp2;
    int max1 = INT_MIN, max2 = INT_MIN;
    int min1 = INT_MAX, min2 = INT_MAX;
 
    // Calculating max1 , min1 and max2, min2
    for (int i = 0; i < n; i++) {
        temp1 = arr[i] + i;
        temp2 = arr[i] - i;
        max1 = max(max1, temp1);
        min1 = min(min1, temp1);
        max2 = max(max2, temp2);
        min2 = min(min2, temp2);
    }
 
    // required maximum ans is max of (max1-min1) and
    // (max2-min2)
    return max((max1 - min1), (max2 - min2));
}
 
// Driven Code
int main()
{
    int arr[] = { 1, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findValue(arr, n) << endl;
 
    return 0;
}
 
// code by AJAY MAKVANA

// Optimized JAVA program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
import java.util.*;
class GFG
{
 
// Return maximum |arr[i] - arr[j]| + |i - j|
static int findValue(int arr[], int n)
{
    int temp1, temp2;
    int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
    int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
 
    // Calculating max1 , min1 and max2, min2
    for (int i = 0; i < n; i++) {
        temp1 = arr[i] + i;
        temp2 = arr[i] - i;
        max1 = Math.max(max1, temp1);
        min1 = Math.min(min1, temp1);
        max2 = Math.max(max2, temp2);
        min2 = Math.min(min2, temp2);
    }
 
    // required maximum ans is max of (max1-min1) and
    // (max2-min2)
    return Math.max((max1 - min1), (max2 - min2));
}
 
// Driven Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 1 };
    int n = arr.length;
 
    System.out.print(findValue(arr, n) +"\n");
}
}
 
// This code is contributed by gauravrajput1.

# Optimized Python program to find maximum value of
# |arr[i] - arr[j]| + |i - j|
import sys
 
# Return maximum |arr[i] - arr[j]| + |i - j|
def findValue(arr, n):
    temp1=0;
    temp2=0;
    max1 = -sys.maxsize;
    max2 = -sys.maxsize;
    min1 = sys.maxsize;
    min2 = sys.maxsize;
 
    # Calculating max1 , min1 and max2, min2
    for i in range(n):
        temp1 = arr[i] + i;
        temp2 = arr[i] - i;
        max1 = max(max1, temp1);
        min1 = min(min1, temp1);
        max2 = max(max2, temp2);
        min2 = min(min2, temp2);
     
    # required maximum ans is max of (max1-min1) and
    # (max2-min2)
    return max((max1 - min1), (max2 - min2));
 
# Driven Code
if __name__ == '__main__':
    arr = [ 1, 2, 3, 1 ];
    n = len(arr);
 
    print(findValue(arr, n));
 
# This code is contributed by umadevi9616

// Optimized JAVA program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
using System;
 
public class GFG {
 
    // Return maximum |arr[i] - arr[j]| + |i - j|
    static int findValue(int[] arr, int n)
    {
        int temp1, temp2;
        int max1 = int.MinValue, max2 = int.MinValue;
        int min1 = int.MaxValue, min2 = int.MaxValue;
 
        // Calculating max1 , min1 and max2, min2
        for (int i = 0; i < n; i++) {
            temp1 = arr[i] + i;
            temp2 = arr[i] - i;
            max1 = Math.Max(max1, temp1);
            min1 = Math.Min(min1, temp1);
            max2 = Math.Max(max2, temp2);
            min2 = Math.Min(min2, temp2);
        }
 
        // required maximum ans is max of (max1-min1) and
        // (max2-min2)
        return Math.Max((max1 - min1), (max2 - min2));
    }
 
    // Driven Code
    public static void Main(String[] args)
    {
        int[] arr = { 1, 2, 3, 1 };
        int n = arr.Length;
 
        Console.Write(findValue(arr, n) + "\n");
    }
}
 
// This code is contributed by gauravrajput1

<script>
// Optimized javascript program to find maximum value of
// |arr[i] - arr[j]| + |i - j|
 
    // Return maximum |arr[i] - arr[j]| + |i - j|
    function findValue(arr , n) {
        var temp1, temp2;
        var max1 = Number.MIN_VALUE, max2 = Number.MIN_VALUE;
        var min1 = Number.MAX_VALUE, min2 = Number.MAX_VALUE;
 
        // Calculating max1 , min1 and max2, min2
        for (i = 0; i < n; i++) {
            temp1 = arr[i] + i;
            temp2 = arr[i] - i;
            max1 = Math.max(max1, temp1);
            min1 = Math.min(min1, temp1);
            max2 = Math.max(max2, temp2);
            min2 = Math.min(min2, temp2);
        }
 
        // required maximum ans is max of (max1-min1) and
        // (max2-min2)
        return Math.max((max1 - min1), (max2 - min2));
    }
 
    // Driven Code
        var arr = [ 1, 2, 3, 1 ];
        var n = arr.length;
 
        document.write(findValue(arr, n) + "\n");
 
// This code is contributed by gauravrajput1
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1) 

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.