Maximum value of arr[i] + arr[j] + i – j for any pair of an array
Given an array arr[] consisting of N integers, the task is to find the maximum value of (arr[i] + arr[j] + i ? j) for any possible pair (i, j) of the given array.
Examples:
Input: arr[] = {1, 9, 3, 6, 5}
Output: 13
Explanation:
The pair of the array having the maximum value of (arr[i] + arr[j] + i ? j) is (1, 3). The value is (arr[1] + arr[3] + 1 – 3) = (9 + 6 + 1 – 3) = 13.Input: arr[] = {6, 2, 5, 6}
Output: 10
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs (i, j) of the given array and find the maximum value of the expression among all possible pairs.
Below is the implementation of the above approach:
C++
// C++ program to for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value of // arr[i] + arr[j] + i - j over all pairs void maximumValue( int arr[], int n) { // Stores the required result int ans = 0; // Traverse over all the pairs (i, j) for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Calculate the value of the // expression and update the // overall maximum value ans = max(ans, arr[i] + arr[j] + i - j); } } // Print the result cout << ans; } // Driven Code int main() { int arr[] = { 1, 9, 3, 6, 5 }; int N = sizeof (arr) / sizeof (arr[0]); maximumValue(arr, N); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to find the maximum value of // arr[i] + arr[j] + i - j over all pairs static void maximumValue( int arr[], int n) { // Stores the required result int ans = 0 ; // Traverse over all the pairs (i, j) for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // Calculate the value of the // expression and update the // overall maximum value ans = Math.max(ans, arr[i] + arr[j] + i - j); } } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 9 , 3 , 6 , 5 }; int N = arr.length; maximumValue(arr, N); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to find the maximum value of # arr[i] + arr[j] + i - j over all pairs def maximumValue(arr, n): # Stores the required result ans = 0 # Traverse over all the pairs (i, j) for i in range (n): for j in range (i + 1 , n): # Calculate the value of the # expression and update the # overall maximum value ans = max (ans, arr[i] + arr[j] + i - j) print (ans) # Driver Code arr = [ 1 , 9 , 3 , 6 , 5 ] N = len (arr) maximumValue(arr, N) # This code is contributed by abhinavjain194 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum value of // arr[i] + arr[j] + i - j over all pairs static void maximumValue( int [] arr, int n) { // Stores the required result int ans = 0; // Traverse over all the pairs (i, j) for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Calculate the value of the // expression and update the // overall maximum value ans = Math.Max(ans, arr[i] + arr[j] + i - j); } } // Print the result Console.Write(ans); } // Driver code static void Main() { int [] arr = { 1, 9, 3, 6, 5 }; int N = arr.Length; maximumValue(arr, N); } } // This code is contributed by abhinavjain194 |
Javascript
<script> // Javascript program to for the above approach var arr = [ 1, 9, 3, 6, 5 ]; // Function to find the maximum value of // arr[i] + arr[j] + i - j over all pairs function maximumValue(arr, n) { // Stores the required result var ans = 0; // Traversing over all the pairs (i, j) for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Calculate the value of the // expression and update the // overall maximum value ans = Math.max(ans, arr[i] + arr[j] + i - j); } } // Print the result document.write(ans); } // Driver code n = arr.length maximumValue(arr, n); // This code is contributed by SoumikMondal </script> |
13
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by breaking the expression (arr[i] + arr[j] + i – j) in two parts: (arr[i] + i) and (arr[j] – j) and then maximize the sum of the maximum value of (arr[i] + i) with all possible value of (arr[i] – i). Follow the steps below to solve the problem:
- Initialize two variables, res with 0 to store the required sum and maxValue with arr[0] to keep track of the maximum value of (arr[i] + i).
- Traverse the given array arr[] over the range [1, N – 1] using the variable i and perform the following steps:
- Store the value of the expression in X as (maxValue + arr[i] – i).
- If the value of X is greater than res, then update the value of res to X.
- If the value of arr[i] + i is greater than maxValue, then update maxValue to (arr[i] + i).
- After completing the above steps, print the value of res as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value // of (arr[i] + arr[j] + i - j) // possible for a pair in the array void maximumValue( int arr[], int n) { // Stores the maximum value // of(arr[i] + i) int maxvalue = arr[0]; // Stores the required result int result = 0; // Traverse the array arr[] for ( int i = 1; i < n; i++) { // Calculate for current pair // and update maximum value result = max(result, maxvalue + arr[i] - i); // Update maxValue if (arr[i] + I) // is greater than maxValue maxvalue = max(maxvalue, arr[i] + i); } // Print the result cout << result; } // Driven Code int main() { int arr[] = { 1, 9, 3, 6, 5 }; int N = sizeof (arr) / sizeof (arr[0]); maximumValue(arr, N); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to find the maximum value // of (arr[i] + arr[j] + i - j) // possible for a pair in the array static void maximumValue( int arr[], int n) { // Stores the maximum value // of(arr[i] + i) int maxvalue = arr[ 0 ]; // Stores the required result int result = 0 ; // Traverse the array arr[] for ( int i = 1 ; i < n; i++) { // Calculate for current pair // and update maximum value result = Math.max(result, maxvalue + arr[i] - i); // Update maxValue if (arr[i] + I) // is greater than maxValue maxvalue = Math.max(maxvalue, arr[i] + i); } // Print the result System.out.println(result); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 9 , 3 , 6 , 5 }; int N = arr.length; maximumValue(arr, N); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to find the maximum value # of (arr[i] + arr[j] + i - j) # possible for a pair in the array def maximumValue(arr, n): # Stores the maximum value # of(arr[i] + i) maxvalue = arr[ 0 ] # Stores the required result result = 0 # Traverse the array arr[] for i in range ( 1 , n): # Calculate for current pair # and update maximum value result = max (result, maxvalue + arr[i] - i) # Update maxValue if (arr[i] + I) # is greater than maxValue maxvalue = max (maxvalue, arr[i] + i) print (result) # Driver code arr = [ 1 , 9 , 3 , 6 , 5 ] N = len (arr) maximumValue(arr, N) # This code is contributed by abhinavjain194 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum value of // arr[i] + arr[j] + i - j over all pairs static void maximumValue( int [] arr, int n) { // Stores the maximum value // of(arr[i] + i) int maxvalue = arr[0]; // Stores the required result int result = 0; // Traverse the array arr[] for ( int i = 1; i < n; i++) { // Calculate for current pair // and update maximum value result = Math.Max(result, maxvalue + arr[i] - i); // Update maxValue if (arr[i] + I) // is greater than maxValue maxvalue = Math.Max(maxvalue, arr[i] + i); } // Print the result Console.Write(result); } // Driver code static void Main() { int [] arr = { 1, 9, 3, 6, 5 }; int N = arr.Length; maximumValue(arr, N); } } // This code is contributed by abhinavjain194 |
Javascript
<script> // Javascript program for the above approach // Function to find the maximum value // of (arr[i] + arr[j] + i - j) // possible for a pair in the array function maximumValue(arr , n) { // Stores the maximum value // of(arr[i] + i) var maxvalue = arr[0]; // Stores the required result var result = 0; // Traverse the array arr for (i = 1; i < n; i++) { // Calculate for current pair // and update maximum value result = Math.max(result, maxvalue + arr[i] - i); // Update maxValue if (arr[i] + I) // is greater than maxValue maxvalue = Math.max(maxvalue, arr[i] + i); } // Print the result document.write(result); } // Driver Code var arr = [ 1, 9, 3, 6, 5 ]; var N = arr.length; maximumValue(arr, N); // This code contributed by Rajput-Ji </script> |
13
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us