Maximize value of (arr[i] – i) – (arr[j] – j) in an array

0 0 8 minutes read

Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. Where i and j vary from 0 to n-1 and n is size of input array arr[].

Examples:

Input : arr[] = {9, 15, 4, 12, 13}
Output : 12
We get the maximum value for i = 1 and j = 2
(15 - 1) - (4 - 2) = 12

Input : arr[] = {-1, -2, -3, 4, 10}
Output : 6
We get the maximum value for i = 4 and j = 2
(10 - 4) - (-3 - 2) = 11

One important observation is, value of (arr[i] – i) – (arr[j] – j) can never be negative. We can always swap i and j to convert a negative value into a positive. So the condition i not equal to j is bogus and doesn’t require an explicit check.

Method 1 (Naive : O(n²)): The idea is to run two loops to consider all possible pairs and keep track of maximum value of expression (arr[i]-i)-(arr[j]-j). Below is the implementation of this idea.

Implementation:

C++

// C++ program to find maximum value (arr[i]-i)
// - (arr[j]-j) in an array.
#include<bits/stdc++.h>
using namespace std;
 
// Returns maximum value of (arr[i]-i) - (arr[j]-j)
int findMaxDiff(int arr[], int n)
{
    if (n < 2)
    {
        cout << "Invalid ";
        return 0;
    }
 
    // Use two nested loops to find the result
    int res = INT_MIN;
    for (int i=0; i<n; i++)
       for (int j=0; j<n; j++)
          if ( res < (arr[i]-arr[j]-i+j) )
            res = (arr[i]-arr[j]-i+j);
 
    return res;
}
 
// Driver program
int main()
{
   int arr[] = {9, 15, 4, 12, 13};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << findMaxDiff(arr, n);
   return 0;
}

Java

// Java program to find maximum value (arr[i]-i)
// - (arr[j]-j) in an array.
import java.util.*;
 
class GFG {
     
// Returns maximum value of
// (arr[i]-i) - (arr[j]-j)
static int findMaxDiff(int arr[], int n) 
{
    if (n < 2) {
    System.out.print("Invalid ");
    return 0;
    }
 
    // Use two nested loops to find the result
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (res < (arr[i] - arr[j] - i + j))
        res = (arr[i] - arr[j] - i + j);
 
    return res;
}
 
// Driver code
public static void main(String[] args) 
{
    int arr[] = {9, 15, 4, 12, 13};
    int n = arr.length;
    System.out.print(findMaxDiff(arr, n));
}
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python program to find
# maximum value (arr[i]-i)
# - (arr[j]-j) in an array.
 
# Returns maximum value of
# (arr[i]-i) - (arr[j]-j)
def findMaxDiff(arr,n):
 
    if (n < 2):
     
        print("Invalid ")
        return 0
     
  
    # Use two nested loops
    # to find the result
    res = -2147483648
    for i in range(n):
        for j in range(n):
            if ( res < (arr[i]-arr[j]-i+j) ):
                res = (arr[i]-arr[j]-i+j)
  
    return res
 
# Driver code
 
arr= [9, 15, 4, 12, 13]
n = len(arr)
 
print(findMaxDiff(arr, n))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find maximum 
// value (arr[i]-i)- (arr[j]-j) 
// in an array.
using System;
class GFG {
     
// Returns maximum value of
// (arr[i]-i) - (arr[j]-j)
static int findMaxDiff(int []arr, int n) 
{
    if (n < 2) {
    Console.WriteLine("Invalid ");
    return 0;
    }
 
    // Use two nested loops to
    // find the result
    int res = int.MinValue;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (res < (arr[i] - arr[j] - i + j))
            res = (arr[i] - arr[j] - i + j);
 
    return res;
}
 
// Driver code
public static void Main() 
{
    int []arr = {9, 15, 4, 12, 13};
    int n = arr.Length;
    Console.WriteLine(findMaxDiff(arr, n));
}
}
 
// This code is contributed by anjuj_67.

PHP

<?php
// PHP program to find maximum value 
// (arr[i]-i) - (arr[j]-j) in an array.
 
// Returns maximum value of 
// (arr[i]-i) - (arr[j]-j)
function findMaxDiff( $arr, $n)
{
    if ($n < 2)
    {
        echo "Invalid ";
        return 0;
    }
 
    // Use two nested loops to 
    // find the result
    $res = PHP_INT_MIN;
    for($i = 0; $i < $n; $i++)
    for($j = 0; $j < $n; $j++)
        if($res < ($arr[$i] - $arr[$j] - $i + $j))
            $res = ($arr[$i] - $arr[$j] - $i + $j);
 
    return $res;
}
 
// Driver Code
$arr = array(9, 15, 4, 12, 13);
$n = count($arr);
echo findMaxDiff($arr, $n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
    // JavaScript program to find maximum 
    // value (arr[i]-i)- (arr[j]-j) 
    // in an array.
     
    // Returns maximum value of
    // (arr[i]-i) - (arr[j]-j)
    function findMaxDiff(arr, n) 
    {
        if (n < 2) {
            document.write("Invalid ");
            return 0;
        }
 
        // Use two nested loops to
        // find the result
        let res = Number.MIN_VALUE;
        for (let i = 0; i < n; i++)
            for (let j = 0; j < n; j++)
                if (res < (arr[i] - arr[j] - i + j))
                    res = (arr[i] - arr[j] - i + j);
 
        return res;
    }
     
    let arr = [9, 15, 4, 12, 13];
    let n = arr.length;
    document.write(findMaxDiff(arr, n));
     
</script>

Output

Auxiliary Space: O(1), since no extra space used.

Method 2 (Tricky : O(n)):

Find maximum value of arr[i] – i in whole array.
Find minimum value of arr[i] – i in whole array.
Return difference of above two values. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Implementation:

C++

// C++ program to find maximum value (arr[i]-i)
// - (arr[j]-j) in an array.
#include<bits/stdc++.h>
using namespace std;
 
// Returns maximum value of (arr[i]-i) - (arr[j]-j)
int findMaxDiff(int a[], int n)
{
    if (n < 2)
    {
        cout << "Invalid ";
        return 0;
    }
 
    // Find maximum of value of arr[i] - i for all
    // possible values of i. Let this value be max_val.
    // Find minimum of value of arr[i] - i for all
    // possible values of i. Let this value be min_val.
    // The difference max_val - min_v
    int min_val = INT_MAX, max_val = 
                           INT_MIN;
    for (int i=0; i<n; i++)
    {
        if ((a[i]-i) > max_val)
            max_val = a[i] - i;
        if ((a[i]-i) < min_val)
            min_val = a[i]-i;
    }
 
    return (max_val - min_val);
}
 
// Driver program
int main()
{
    int arr[] = {9, 15, 4, 12, 13};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << findMaxDiff(arr, n);
    return 0;
}

Java

// Java program to find maximum value (arr[i]-i)
// - (arr[j]-j) in an array.
import java.io.*;
 
class GFG {
 
    // Returns maximum value of (arr[i]-i) - 
    // (arr[j]-j)
    static int findMaxDiff(int arr[], int n)    
    {
        if (n < 2)
        {
            System.out.println("Invalid ");
            return 0;
        }
 
        // Find maximum of value of arr[i] - i 
        // for all possible values of i. Let 
        // this value be max_val. Find minimum
        // of value of arr[i] - i for all
        // possible values of i. Let this value
        // be min_val. The difference max_val -
        // min_v
        int min_val = Integer.MAX_VALUE,
            max_val = Integer.MIN_VALUE;
         
        for (int i = 0; i < n; i++)
        {
            if ((arr[i]-i) > max_val)
                max_val = arr[i] - i;
                 
            if ((arr[i]-i) < min_val)
                min_val = arr[i]-i;
        }
 
        return (max_val - min_val);
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int arr[] = {9, 15, 4, 12, 13};
        int n = arr.length;
        System.out.println(findMaxDiff(arr, n));
    }
}
// This code is contributed by Prerna Saini

Python3

# Python 3 program to find maximum value
# (arr[i]-i) - (arr[j]-j) in an array.
import sys 
 
# Returns maximum value of 
# (arr[i]-i) - (arr[j]-j)
def findMaxDiff(a, n):
    if (n < 2):
        print("Invalid ")
        return 0
 
    # Find maximum of value of arr[i] - i
    # for all possible values of i. Let 
    # this value be max_val. Find minimum
    # of value of arr[i] - i for all possible 
    # values of i. Let this value be min_val.
    # The difference max_val - min_v
    min_val = sys.maxsize
    max_val = -sys.maxsize - 1
    for i in range(n):
        if ((a[i] - i) > max_val):
            max_val = a[i] - i
        if ((a[i] - i) < min_val):
            min_val = a[i] - i
 
    return (max_val - min_val)
 
# Driver Code
if __name__ == '__main__':
    arr = [9, 15, 4, 12, 13]
    n = len(arr)
    print(findMaxDiff(arr, n))
 
# This code is contributed by Rajput-Ji

C#

// C# program to find maximum value (arr[i]-i)
// - (arr[j]-j) in an array.
using System;
  
class GFG {
  
    // Returns maximum value of (arr[i]-i) - 
    // (arr[j]-j)
    static int findMaxDiff(int []arr, int n)    
    {
        if (n < 2)
        {
            Console.Write("Invalid ");
            return 0;
        }
  
        // Find maximum of value of arr[i] - i 
        // for all possible values of i. Let 
        // this value be max_val. Find minimum
        // of value of arr[i] - i for all
        // possible values of i. Let this value
        // be min_val. The difference max_val -
        // min_v
        int min_val = int.MaxValue,
            max_val = int.MinValue;
          
        for (int i = 0; i < n; i++)
        {
            if ((arr[i] - i) > max_val)
                max_val = arr[i] - i;
                  
            if ((arr[i] - i) < min_val)
                min_val = arr[i] - i;
        }
  
        return (max_val - min_val);
    }
  
    // Driver program
    public static void Main()
    {
        int []arr = {9, 15, 4, 12, 13};
        int n = arr.Length;
        Console.Write(findMaxDiff(arr, n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find maximum value
// (arr[i]-i) - (arr[j]-j) in an array.
 
// Returns maximum value of 
// (arr[i]-i) - (arr[j]-j)
function findMaxDiff($a, $n)
{
    if ($n < 2)
    {
        echo "Invalid ";
        return 0;
    }
 
    // Find maximum of value of arr[i] - i 
    // for all possible values of i. Let 
    // this value be max_val. Find minimum 
    // of value of arr[i] - i for all
    // possible values of i. Let this value 
    // be min_val. The difference max_val - min_v
    $min_val = PHP_INT_MAX;
    $max_val = PHP_INT_MIN;
    for ($i = 0; $i < $n; $i++)
    {
        if (($a[$i] - $i) > $max_val)
            $max_val = $a[$i] - $i;
        if (($a[$i] - $i) < $min_val)
            $min_val = $a[$i] - $i;
    }
 
    return ($max_val - $min_val);
}
 
// Driver Code
$arr = array(9, 15, 4, 12, 13);
$n = sizeof($arr);
echo findMaxDiff($arr, $n);
 
// This code is contributed by Sachin.
?>

Javascript

<script>
 
    // Javascript program to find
    // maximum value (arr[i]-i)
    // - (arr[j]-j) in an array.
     
    // Returns maximum value of (arr[i]-i) -
    // (arr[j]-j)
    function findMaxDiff(arr, n)   
    {
        if (n < 2)
        {
            document.write("Invalid ");
            return 0;
        }
   
        // Find maximum of value of arr[i] - i
        // for all possible values of i. Let
        // this value be max_val. Find minimum
        // of value of arr[i] - i for all
        // possible values of i. Let this value
        // be min_val. The difference max_val -
        // min_v
        let min_val =
        Number.MAX_VALUE, max_val = Number.MIN_VALUE;
           
        for (let i = 0; i < n; i++)
        {
            if ((arr[i] - i) > max_val)
                max_val = arr[i] - i;
                   
            if ((arr[i] - i) < min_val)
                min_val = arr[i] - i;
        }
   
        return (max_val - min_val);
    }
     
    let arr = [9, 15, 4, 12, 13];
    let n = arr.length;
    document.write(findMaxDiff(arr, n));
       
</script>

Output

Auxiliary Space: O(1), since no extra space used.

This article is contributed by Shivam Agrawal. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!