本文概述

• C++
• C
• Java
• Python3
• C#
• PHP
• C++
• Java
• Python3
• C#
• Python3
• C++
• C
• Java
• Python3
• C#
• PHP

给定一个数组arr[], 找到最大j – i, 使得arr[j] > arr[i]。
例子 ：

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6(j = 7, i = 1)Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0)Input:{1, 2, 3, 4, 5, 6} Output: 5(j = 5, i = 0)Input:{6, 5, 4, 3, 2, 1} Output: -1

方法1(简单但效率低下)
运行两个循环。在外部循环中, 从左开始一个接一个地选择元素。在内部循环中, 将拾取的元素与从右侧开始的元素进行比较。当你看到一个大于选取的元素的元素时, 请停止内部循环, 并保持当前的最大j-i更新。
C++

#include < bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j> i; --j) { if (arr[j]> arr[i] & & maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) /sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout < < "\n" < < maxDiff; return 0; } //This code is contributed //by Akanksha Rai(Abby_akku)

C

#include < stdio.h> /* For a given array arr[], returns the maximum j – i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j> i; --j) { if (arr[j]> arr[i] & & maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) /sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); printf ( "\n %d" , maxDiff); getchar (); return 0; }

Java

class FindMaximum { /* For a given array arr[], returns the maximum j-i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = - 1 ; int i, j; for (i = 0 ; i < n; ++i) { for (j = n - 1 ; j> i; --j) { if (arr[j]> arr[i] & & maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } /* Driver program to test above functions */ public static void main(String[] args) { FindMaximum max = new FindMaximum(); int arr[] = { 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 }; int n = arr.length; int maxDiff = max.maxIndexDiff(arr, n); System.out.println(maxDiff); } }

Python3

# Python3 program to find the maximum # j – i such that arr[j]> arr[i]# For a given array arr[], returns # the maximum j – i such that # arr[j]> arr[i] def maxIndexDiff(arr, n): maxDiff = - 1 for i in range ( 0 , n): j = n - 1 while (j> i): if arr[j]> arr[i] and maxDiff < (j - i): maxDiff = j - i; j - = 1return maxDiff # driver code arr = [ 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This article is contributed by Smitha Dinesh Semwal

C#

//C# program to find the maximum //j – i such that arr[j]> arr[i] using System; class GFG { //For a given array arr[], returns //the maximum j-i such that arr[j]> arr[i] static int maxIndexDiff( int [] arr, int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j> i; --j) { if (arr[j]> arr[i] & & maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } //Driver program public static void Main() { int [] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } //This Code is Contributed by Sam007

PHP

< ?php //PHP program to find the maximum //j – i such that arr[j]> arr[i] //For a given array arr[], returns //the maximum j – i such that //arr[j]> arr[i] function maxIndexDiff( $arr , $n ) { $maxDiff = -1; for ( $i = 0; $i < $n ; ++ $i ) { for ( $j = $n - 1; $j> $i ; -- $j ) { if ( $arr[ $j ]> $arr[ $i ] & & $maxDiff < ( $j - $i )) $maxDiff = $j - $i ; } } return $maxDiff ; } //Driver Code $arr = array (9, 2, 3, 4, 5, 6, 7, 8, 18, 0); $n = count ( $arr ); $maxDiff = maxIndexDiff( $arr , $n ); echo $maxDiff ; //This code is contributed by Sam007 ?>

输出如下：

8

时间复杂度：O(n ^ 2)
方法2 –
改进蛮力算法并查找BUD, 即瓶颈, 不必要和重复的作品。快速观察实际上表明, 我们一直在寻找从数组末尾到当前索引的第一个最大元素。我们可以看到, 我们试图一次又一次地为数组中的每个元素找到最大的元素。假设我们有一个数组, 例如[1, 5, 12, 4, 9], 现在我们知道9是大于1、5和4的元素, 但是为什么我们需要一次又一次地找到它。实际上, 我们可以跟踪从数组结尾到开头的最大数量。这种方法将帮助我们更好地理解, 并且即兴采访也很容易。
方法：

1. 从末尾遍历数组, 并跟踪当前索引右边的最大数字, 包括self
2. 现在我们有了一个单调的递减数组, 并且我们知道可以使用二进制搜索找到最右边的较大元素的索引
3. 现在, 我们将仅对数组中的每个元素使用二进制搜索, 并存储索引的最大差值, 就是这样。

C++

/* For a given array arr[], calculates the maximum j – i such that arr[j]> arr[i] */ #include < bits/stdc++.h> using namespace std; int main() { vector< long long int> v{ 34, 8, 10, 3, 2, 80, 30, 33, 1 }; int n = v.size(); vector< long long int> maxFromEnd(n + 1, INT_MIN); //create an array maxfromEnd for ( int i = v.size() - 1; i> = 0; i--) { maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]); } int result = 0; for ( int i = 0; i < v.size(); i++) { int low = i + 1, high = v.size() - 1, ans = i; while (low < = high) { int mid = (low + high) /2; if (v[i] < = maxFromEnd[mid]) { //we store this as current answer and look //for further larger number to the right side ans = max(ans, mid); low = mid + 1; } else { high = mid - 1; } } //keeping a track of the //maximum difference in indices result = max(result, ans - i); } cout < < result < < endl; }

Java

//Java program to implement //the above approach //For a given array arr[], //calculates the maximum j – i //such that arr[j]> arr[i] import java.util.*; class GFG{ public static void main(String[] args) { int []v = { 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 }; int n = v.length; int []maxFromEnd = new int [n + 1 ]; Arrays.fill(maxFromEnd, Integer.MIN_VALUE); //Create an array maxfromEnd for ( int i = v.length - 1 ; i> = 0 ; i--) { maxFromEnd[i] = Math.max(maxFromEnd[i + 1 ], v[i]); } int result = 0 ; for ( int i = 0 ; i < v.length; i++) { int low = i + 1 , high = v.length - 1 , ans = i; while (low < = high) { int mid = (low + high) /2 ; if (v[i] < = maxFromEnd[mid]) { //We store this as current //answer and look for further //larger number to the right side ans = Math.max(ans, mid); low = mid + 1 ; } else { high = mid - 1 ; } }//Keeping a track of the //maximum difference in indices result = Math.max(result, ans - i); } System.out.print(result + "\n" ); } } //This code is contributed by shikhasingrajput

Python3

# Python3 program to implement # the above approach # For a given array arr, # calculates the maximum j – i # such that arr[j]> arr[i] # Driver code if __name__ = = '__main__' :v = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ]; n = len (v); maxFromEnd = [ - 38749432 ] * (n + 1 ); # Create an array maxfromEnd for i in range (n - 1 , 0 , - 1 ): maxFromEnd[i] = max (maxFromEnd[i + 1 ], v[i]); result = 0 ; for i in range ( 0 , n): low = i + 1 ; high = n - 1 ; ans = i; while (low < = high): mid = int ((low + high) /2 ); if (v[i] < = maxFromEnd[mid]):# We store this as current # answer and look for further # larger number to the right side ans = max (ans, mid); low = mid + 1 ; else : high = mid - 1 ; # Keeping a track of the # maximum difference in indices result = max (result, ans - i); print (result, end = ""); # This code is contributed by Rajput-Ji

C#

//C# program to implement //the above approach //For a given array []arr, //calculates the maximum j – i //such that arr[j]> arr[i] using System; class GFG{ public static void Main(String[] args) { int []v = {34, 8, 10, 3, 2, 80, 30, 33, 1}; int n = v.Length; int []maxFromEnd = new int [n + 1]; for ( int i = 0; i < maxFromEnd.Length; i++) maxFromEnd[i] = int .MinValue; //Create an array maxfromEnd for ( int i = v.Length - 1; i> = 0; i--) { maxFromEnd[i] = Math.Max(maxFromEnd[i + 1], v[i]); } int result = 0; for ( int i = 0; i < v.Length; i++) { int low = i + 1, high = v.Length - 1, ans = i; while (low < = high) { int mid = (low + high) /2; if (v[i] < = maxFromEnd[mid]) { //We store this as current //answer and look for further //larger number to the right side ans = Math.Max(ans, mid); low = mid + 1; } else { high = mid - 1; } } //Keeping a track of the //maximum difference in indices result = Math.Max(result, ans - i); } Console.Write(result + "\n" ); } } //This code is contributed by shikhasingrajput

输出如下：

6

时间复杂度：
O(N * log(N))
空间复杂度：O(n)
方法3 O(nLgn)
在特别注意重复项之后, 使用哈希和排序以小于二次复杂度的方式解决此问题。
方法：

1. 遍历数组并将每个元素的索引存储在列表中(以处理重复项)。
2. 对数组进行排序。
3. 现在遍历数组, 并跟踪i和j的最大差。
4. 对于j, 请考虑该元素可能的索引列表中的最后一个索引, 而对于我, 请考虑该列表中的第一个索引。 (因为索引是按升序附加的)。
5. 不断更新最大差值, 直到数组末尾。

Python3

# Python3 implementation of the above approach n = 9 a = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ] # To store the index of an element. index = dict () for i in range (n): if a[i] in index: # append to list (for duplicates) index[a[i]].append(i) else : # if first occurrence index[a[i]] = [i] # sort the input array a.sort() maxDiff = 0 # Temporary variable to keep track of minimum i temp = n for i in range (n): if temp> index[a[i]][ 0 ]: temp = index[a[i]][ 0 ] maxDiff = max (maxDiff, index[a[i]][ - 1 ] - temp) print (maxDiff)

输出如下：

6

时间复杂度：O(N * log(N))
方法4(有效)
为了解决这个问题, 我们需要获得arr[]的两个最佳索引：左索引i和右索引j。对于元素arr[i], 如果arr[i]左侧的元素小于arr[i], 则无需为左索引考虑arr[i]。同样, 如果arr[j]的右侧有一个更大的元素, 那么对于正确的索引, 我们不需要考虑这个j。因此, 我们构造了两个辅助数组LMin []和RMax [], 使得LMin [i]在包含arr[i]的arr[i]左侧保留最小的元素, 而RMax [j]在arr[i]右侧保留最大的元素arr[j]包括arr[j]。构建完这两个辅助数组后, 我们从左到右遍历这两个数组。在遍历LMin []和RMa []时, 如果我们看到LMin [i]大于RMax [j], 则必须向前移动LMin [](或执行i ++), 因为LMin [i]左侧的所有元素都是大于或等于LMin [i]。否则, 我们必须继续前进RMax [j], 以寻找更大的j – i值。
感谢celicom为这种方法建议算法。
C++

#include < bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int * LMin = new int [( sizeof ( int ) * n)]; int * RMax = new int [( sizeof ( int ) * n)]; /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1] = arr[n - 1]; for (j = n - 2; j> = 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); /* Traverse both arrays from left to right to find optimum j - i. This process is similar to merge() of MergeSort */ i = 0, j = 0, maxDiff = -1; while (j < n & & i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } //Driver Code int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) /sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout < < maxDiff; return 0; } //This code is contributed by rathbhupendra

C

#include < stdio.h> /* Utility Functions to get max and minimum of two integers */ int max( int x, int y) { return x> y ? x : y; } int min( int x, int y) { return x < y ? x : y; } /* For a given array arr[], returns the maximum j – i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int * LMin = ( int *) malloc ( sizeof ( int ) * n); int * RMax = ( int *) malloc ( sizeof ( int ) * n); /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1] = arr[n - 1]; for (j = n - 2; j> = 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); /* Traverse both arrays from left to right to find optimum j - i This process is similar to merge() of MergeSort */ i = 0, j = 0, maxDiff = -1; while (j < n & & i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } /* Driver program to test above functions */ int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) /sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); printf ( "\n %d" , maxDiff); getchar (); return 0; }

Java

class FindMaximum { /* Utility Functions to get max and minimum of two integers */ int max( int x, int y) { return x> y ? x : y; } int min( int x, int y) { return x < y ? x : y; } /* For a given array arr[], returns the maximum j-i such that arr[j]> arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int RMax[] = new int [n]; int LMin[] = new int [n]; /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[ 0 ] = arr[ 0 ]; for (i = 1 ; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1 ]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1 ] = arr[n - 1 ]; for (j = n - 2 ; j> = 0 ; --j) RMax[j] = max(arr[j], RMax[j + 1 ]); /* Traverse both arrays from left to right to find optimum j - i This process is similar to merge() of MergeSort */ i = 0 ; j = 0 ; maxDiff = - 1 ; while (j < n & & i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1 ; } else i = i + 1 ; } return maxDiff; } /* Driver program to test the above functions */ public static void main(String[] args) { FindMaximum max = new FindMaximum(); int arr[] = { 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 }; int n = arr.length; int maxDiff = max.maxIndexDiff(arr, n); System.out.println(maxDiff); } }

Python3

# Utility Functions to get max # and minimum of two integers def max (a, b): if (a> b): return a else : return b def min (a, b): if (a < b): return a else : return b # For a given array arr[], # returns the maximum j - i # such that arr[j]> arr[i] def maxIndexDiff(arr, n): maxDiff = 0 ; LMin = [ 0 ] * n RMax = [ 0 ] * n # Construct LMin[] such that # LMin[i] stores the minimum # value from (arr[0], arr[1], # ... arr[i]) LMin[ 0 ] = arr[ 0 ] for i in range ( 1 , n): LMin[i] = min (arr[i], LMin[i - 1 ]) # Construct RMax[] such that # RMax[j] stores the maximum # value from (arr[j], arr[j + 1], # ..arr[n-1]) RMax[n - 1 ] = arr[n - 1 ] for j in range (n - 2 , - 1 , - 1 ): RMax[j] = max (arr[j], RMax[j + 1 ]); # Traverse both arrays from left # to right to find optimum j - i # This process is similar to # merge() of MergeSort i, j = 0 , 0 maxDiff = - 1 while (j < n and i < n): if (LMin[i] < RMax[j]): maxDiff = max (maxDiff, j - i) j = j + 1 else : i = i + 1 return maxDiff # Driver Code if (__name__ = = '__main__' ): arr = [ 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This code is contributed # by gautam karakoti

C#

//C# program to find the maximum //j – i such that arr[j]> arr[i] using System; class GFG { //Utility Functions to get max //and minimum of two integers static int max( int x, int y) { return x> y ? x : y; } static int min( int x, int y) { return x < y ? x : y; } //For a given array arr[], returns //the maximum j-i such thatarr[j]> arr[i] static int maxIndexDiff( int [] arr, int n) { int maxDiff; int i, j; int [] RMax = new int [n]; int [] LMin = new int [n]; //Construct LMin[] such that LMin[i] //stores the minimum value //from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); //Construct RMax[] such that //RMax[j] stores the maximum value //from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j> = 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); //Traverse both arrays from left //to right to find optimum j - i //This process is similar to merge() //of MergeSort i = 0; j = 0; maxDiff = -1; while (j < n & & i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } //Driver program public static void Main() { int [] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } //This Code is Contributed by Sam007

PHP

< ?php //PHP program to find the maximum //j – i such that arr[j]> arr[i] //For a given array arr[], //returns the maximum j - i //such that arr[j]> arr[i] function maxIndexDiff( $arr , $n ) { $maxDiff = 0; $LMin = array_fill (0, $n , NULL); $RMax = array_fill (0, $n , NULL); //Construct LMin[] such that //LMin[i] stores the minimum //value from (arr[0], arr[1], //... arr[i]) $LMin [0] = $arr[0]; for ( $i = 1; $i < $n ; $i ++) $LMin [ $i ] = min( $arr[ $i ], $LMin [ $i - 1]); //Construct RMax[] such that //RMax[j] stores the maximum //value from (arr[j], arr[j+1], //..arr[n-1]) $RMax [ $n - 1] = $arr[ $n - 1]; for ( $j = $n - 2; $j> = 0; $j --) $RMax [ $j ] = max( $arr[ $j ], $RMax [ $j + 1]); //Traverse both arrays from left //to right to find optimum j - i //This process is similar to //merge() of MergeSort $i = 0; $j = 0; $maxDiff = -1; while ( $j < $n & & $i < $n ) if ( $LMin [ $i ] < $RMax [ $j ]) { $maxDiff = max( $maxDiff , $j - $i ); $j = $j + 1; } else $i = $i + 1; return $maxDiff ; } //Driver Code $arr = array (9, 2, 3, 4, 5, 6, 7, 8, 18, 0); $n = sizeof( $arr ); $maxDiff = maxIndexDiff( $arr , $n ); echo $maxDiff ; //This code is contributed //by ChitraNayal ?>

输出如下：

8

时间复杂度：O(n)
辅助空间：O(n)
【给定数组arr[]，找到最大j – i，使得arr[j]大于arr[i]】如果你发现上述代码/算法有误, 请写评论, 或者找到其他解决相同问题的方法。

推荐阅读

• 

  在游戏圈中哪几款神作玩家一直在等？
• 

  高密度gpu 图片分析
• 

  搞笑短信网 超搞笑短信铃声
• 

  华为手机日历如何去消已建的活动
• 

  美容霜什么时候用
• 

  癌细胞|癌细胞转移、扩散前有什么表现？手术难道就不能根治吗？答案来了
• 

  印度将会成为人口第一，中国将失去人口第一大国
• 

  什么是一元回归分析法
• 

  安卓外国聊天视频,即时通讯软件可结合外国person聊天
• 

  ironhe苹果将推出「CarPlay升级版」可用iPhone控制座椅
• 

  ios14负一屏设置方法
• 

  wOPPO未来玩机发布会开启，”三屏“联动打造超能玩家硬核体验
• 

  怎样挑选真的杭白菊
• 

  皇帝柑的皮有什么用
• 

  2019-01-22复盘
• 

  尼康d300怎么调模式 尼康d300模式说明书
• 

  隐瞒犯罪所得是什么罪名 隐瞒犯罪所得罪既遂怎么处罚?
• 

  签劳动合同起止日期和终止日期怎么确定的
• 

  汽车车身树脂怎么清洗 汽车有树脂怎么清洗
• 

  魅族pro6呼吸灯在哪里设置

• Python OpenCV cv2.rectangle()方法绘制矩形示例
• C++中的智能指针及其类型介绍
• C#中的链表实现代码示例和原理解释
• PHP Ds\Vector contains()函数用法详细示例
• Dijkstra算法（邻接表表示的算法实现|贪婪算法S8）
• TCP连接终止详细指南和解读
• JavaScript如何设置input字段的值（代码示例）
• JavaScript while循环语句例子详细指南
• Win8 Word文件默认为只读怎样处理？