给定一个数组，arr[]找到（arr[i]-i）-（arr[j]-j）的最大值，其中i不等于j。其中i和j从0到n-1变化，n是输入数组arr[]的大小。 例如：
null
Input : arr[] = {9, 15, 4, 12, 13}Output : 12We get the maximum value for i = 1 and j = 2(15 - 1) - (4 - 2) = 12Input : arr[] = {-1, -2, -3, 4, 10}Output : 6We get the maximum value for i = 4 and j = 2(10 - 4) - (-3 - 2) = 11
一个重要的观察结果是，（arr[i]-i）-（arr[j]-j）的值永远不能为负。我们总是可以交换i和j，将负值转换成正值。所以i不等于j的条件是假的，不需要显式检查。 方法1（天真：O（n） 2. )) 这个想法是运行两个循环来考虑所有可能的对，并跟踪表达式的最大值（ARR [i] -i）-（ARR[J] -J）。下面是这个想法的实施。
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> |
输出：
12
方法2（技巧：O（n）） 1） 在整个数组中找到arr[i]–i的最大值。 2） 求整个数组中arr[i]–i的最小值。 3） 返回上述两个值的差值。
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> |
输出：
12
本文由 希瓦姆·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
