Given an array with input size n, find the maximum value of (a[i] + i) * (a[j] + j) where i is not equal to j.
Note that i and j vary from 0 to n-1 .
Examples:
Input : a[] = [4,5,3,1,10] Output : 84 Explanation: We get the maximum value for i = 4 and j = 1 (10 + 4) * (5 + 1) = 84 Input : a[] = [10,0,0,0,-1] Output : 30 Explanation: We get the maximum value for i = 0 and j = 3 (10 + 0) * (0 + 3) = 30
Naive approach: The simplest way is to run two loops to consider all possible pairs and keep track of maximum value of expression (a[i]+i)*(a[j]+j). Below is Python implementation of this idea. Time complexity will be O(n*n) where n is the input size.
Implementation:
C++
// C++ program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers. maxval() // returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to j#include<bits/stdc++.h>using namespace std;int maxval(int a[], int n) { // at-least there must be two elements // in array if (n < 2) { return -99999; } // calculate maximum value int max = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int x = (a[i] + i) * (a[j] + j); if (max < x) { max = x; } } } return max; } // test the function int main() { int arr[] = {4, 5, 3, 1, 10}; int len = sizeof(arr)/sizeof(arr[0]); cout<<(maxval(arr, len)); } // This code is contributed by// Shashank_Sharma |
Java
// Java program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers. maxval() // returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to jpublic class GFG {// Python static int maxval(int a[], int n) { // at-least there must be two elements // in array if (n < 2) { return -99999; } // calculate maximum value int max = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int x = (a[i] + i) * (a[j] + j); if (max < x) { max = x; } } } return max; }// test the function public static void main(String args[]) { int arr[] = {4, 5, 3, 1, 10}; int len = arr.length; System.out.println(maxval(arr, len)); }}/*This code is contributed by 29AjayKumar*/ |
Python3
# Python program to find maximum value (a[i]+i)*# (a[j]+j) in an array of integers. maxval() # returns maximum value of (a[i]+i)*(a[j]+j)# where i is not equal to jdef maxval(a,n): # at-least there must be two elements # in array if (n < 2): return -99999 # calculate maximum value max = 0 for i in range(n): for j in range(i+1,n): x = (a[i]+i)*(a[j]+j) if max < x: max = x return max# test the functionprint(maxval([4,5,3,1,10],5)) |
C#
// C# program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers. maxval() // returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to jusing System;public class GFG {// Python static int maxval(int []a, int n) { // at-least there must be two elements // in array if (n < 2) { return -99999; } // calculate maximum value int max = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int x = (a[i] + i) * (a[j] + j); if (max < x) { max = x; } } } return max; }// test the function public static void Main() { int []arr = {4, 5, 3, 1, 10}; int len = arr.Length; Console.Write(maxval(arr, len)); }} /*This code is contributed by 29AjayKumar*/ |
PHP
<?php// PHP program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers. maxval() // returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to on function maxval($a, $n) { // at-least there must be two // elements in array if ($n < 2) { return -99999; } // calculate maximum value $max = 0; for ($i = 0; $i < $n; $i++) { for ($j = $i + 1; $j < $n; $j++) { $x = ($a[$i] + $i) * ($a[$j] + $j); if ($max < $x) { $max = $x; } } } return $max;}// Driver Code$arr = array(4, 5, 3, 1, 10);$len = count($arr);echo (maxval($arr, $len));// This code is contributed by ajit?> |
Javascript
<script> // Javascript program to find maximum value (a[i]+i)* // (a[j]+j) in an array of integers. maxval() // returns maximum value of (a[i]+i)*(a[j]+j) // where i is not equal to j function maxval(a, n) { // at-least there must be two elements // in array if (n < 2) { return -99999; } // calculate maximum value let max = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let x = (a[i] + i) * (a[j] + j); if (max < x) { max = x; } } } return max; } let arr = [4, 5, 3, 1, 10]; let len = arr.length; document.write(maxval(arr, len)); </script> |
Output
84
Efficient approach:
An efficient method is to find maximum value of a[i] + i along with the second maximum value of a[i] + i in the array. Return the product of the two values.
Finding maximum and second maximum can be done in a single traversal of the array.
So,Time complexity will be O(n).
Below is the implementation of this idea.
C++
// C++ program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers// maxval() returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to j#include<bits/stdc++.h>using namespace std;#define MAX 5int maxval(int a[MAX], int n) { // there must be at-least two // elements in the array if (n < 2) { cout << "Invalid Input"; return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) int max1 = 0, max2 = 0; for (int i = 0; i < n; i++) { int x = a[i] + i; // If current element x is greater than // first then update first and second if (x > max1) { max2 = max1; max1 = x; } // if x is in between max1 and // max2 then update max2 else if (x > max2 & x != max1) { max2 = x; } } return (max1 * max2);}// Driver Codeint main(){ int arr[] = {4, 5, 3, 1, 10}; int len = sizeof(arr)/arr[0]; cout << maxval(arr, len);}// This code is contributed // by Akanksha Rai |
C
// C program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers// maxval() returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to j#include<stdio.h>#include<string.h>#define MAX 5int maxval(int a[MAX], int n) { // there must be at-least two elements in // the array if (n < 2) { printf("Invalid Input"); return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) int max1 = 0, max2 = 0; for (int i = 0; i < n; i++) { int x = a[i] + i; // If current element x is greater than // first then update first and second if (x > max1) { max2 = max1; max1 = x; }// if x is in between max1 and // max2 then update max2 else if (x > max2 & x != max1) { max2 = x; } } return (max1 * max2); // test the function}int main() { int arr[] = {4, 5, 3, 1, 10}; int len = sizeof(arr)/arr[0]; printf("%d",maxval(arr, len));}// This code is contributed by 29AjayKumar |
Java
// Java program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers// maxval() returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to jclass GFG { static int maxval(int[] a, int n) { // there must be at-least two elements in // the array if (n < 2) { System.out.print("Invalid Input"); return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) int max1 = 0, max2 = 0; for (int i = 0; i < n; i++) { int x = a[i] + i; // If current element x is greater than // first then update first and second if (x > max1) { max2 = max1; max1 = x; } // if x is in between max1 and // max2 then update max2 else if (x > max2 & x != max1) { max2 = x; } } return (max1 * max2);// test the function } public static void main(String[] args) { int arr[] = {4, 5, 3, 1, 10}; int len = arr.length; System.out.println(maxval(arr, len)); }}// This code is contributed by Rajput-Ji |
Python3
# Python program to find maximum value (a[i]+i)*# (a[j]+j) in an array of integers# maxval() returns maximum value of (a[i]+i)*(a[j]+j)# where i is not equal to jdef maxval(a,n): # there must be at-least two elements in # the array if (n < 2): print("Invalid Input") return -9999 # max1 will store the maximum value of # (a[i]+i) # max2 will store the second maximum value # of (a[i]+i) (max1, max2) = (0, 0) for i in range(n): x = a[i] + i # If current element x is greater than # first then update first and second if (x > max1): max2 = max1 max1 = x # if x is in between max1 and # max2 then update max2 elif (x > max2 and x != max1): max2 = x return(max1*max2)# test the functionprint(maxval([4,5,3,1,10],5)) |
C#
// C# program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers// maxval() returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to jusing System; public class GFG { static int maxval(int[] a, int n) { // there must be at-least two elements in // the array if (n < 2) { Console.WriteLine("Invalid Input"); return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) int max1 = 0, max2 = 0; for (int i = 0; i < n; i++) { int x = a[i] + i; // If current element x is greater than // first then update first and second if (x > max1) { max2 = max1; max1 = x; } // if x is in between max1 and // max2 then update max2 else if (x > max2 & x != max1) { max2 = x; } } return (max1 * max2); // test the function } public static void Main() { int []arr = {4, 5, 3, 1, 10}; int len = arr.Length; Console.WriteLine(maxval(arr, len)); }} // This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP program to find maximum value (a[i]+i)*// (a[j]+j) in an array of integers// maxval() returns maximum value of (a[i]+i)*(a[j]+j)// where i is not equal to j// $MAX = 5;function maxval($a, $n){ // there must be at-least two elements in // the array if ($n < 2) { echo ("Invalid Input"); return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) $max1 = 0; $max2 = 0; for ($i = 0; $i < $n; $i++) { $x = $a[$i] + $i; // If current element x is greater than // first then update first and second if ($x > $max1) { $max2 = $max1; $max1 = $x; } // if x is in between max1 and // max2 then update max2 else if (($x > $max2) & ($x != $max1)) { $max2 = $x; } } return ($max1 * $max2);}// Driver Code$arr = array(4, 5, 3, 1, 10);$len = count($arr);echo maxval($arr, $len);// This code is contributed by ajit.?> |
Javascript
<script> // Javascript program to find maximum value (a[i]+i)* // (a[j]+j) in an array of integers // maxval() returns maximum value of (a[i]+i)*(a[j]+j) // where i is not equal to j function maxval(a, n) { // there must be at-least two elements in // the array if (n < 2) { document.write("Invalid Input"); return -9999; } // max1 will store the maximum value of // (a[i]+i) // max2 will store the second maximum value // of (a[i]+i) let max1 = 0, max2 = 0; for (let i = 0; i < n; i++) { let x = a[i] + i; // If current element x is greater than // first then update first and second if (x > max1) { max2 = max1; max1 = x; } // if x is in between max1 and // max2 then update max2 else if (x > max2 & x != max1) { max2 = x; } } return (max1 * max2); // test the function } let arr = [4, 5, 3, 1, 10]; let len = arr.length; document.write(maxval(arr, len)); </script> |
Output
84
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!