# 给定数组arr[]，找到最大j – i，使得arr[j]大于arr[i]

2021年4月7日18:49:25 发表评论 774 次浏览

## 本文概述

``````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``````

## 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 - = 1

return maxDiff

# driver code
arr = [ 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 ]
n = len (arr)
maxDiff = maxIndexDiff(arr, n)
print (maxDiff)

## 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``

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
//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
//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))

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``

## 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``