## Introduction

This blog covers one of the many exciting array problems. Arrays are among the most important and often asked data structures in programming contests and technical interviews. There are various standard array problems and techniques. This blog tackles a coding task that involves finding the maximum j â€“ i such that arr[j] > arr[i] in the array.

Also See, __Array Implementation of Queue__ and __Rabin Karp Algorithm____.__

### Problem Statement

Ninja is on holiday, but his college professor has given him an assignment. He has been given an array and is asked to find the maximum j â€“ i value such that arr[j] > arr[i]. Can you help him to enjoy his holiday by solving this problem?

### Sample Examples

**Example 1**

**Input**

**Output**

`4`

**Explanation: **Out of all the value pairs for which arr[j] > arr[i], condition is true, the maximum value of j-i is 4.

**Example 2**

**Input**

**Output**

`6`

**Explanation: **Out of all the value pairs for which arr[j] > arr[i], condition is true, the maximum value of j-i is 6.

## Brute-Force Approach

We run two loops from left and right, respectively. We compare the two values on loops, and if we find an element such that arr[j] > arr[i], we update the maximum value of j-i maintained throughout the loop run.

### Algorithm

1. We start two loops through the array.

2. Pick elements from the left one by one by the outer loop.

3. Compare the selected element to the items starting from the right side in the inner loop.

4. When you see an element larger than the selected element, stop the inner loop and update the maximum j-i value till now.

5. Return the maximum value maintained till now.

### Implementation

```
// Brute-force approach
#include <bits/stdc++.h>
using namespace std;
int valCalculator(int nums[], int n)
{
int m = -1;
int i, j;
// initiate two loops to compare array values from left and right
for (i = 0; i < n; ++i)
{
for (j = n - 1; j > i; --j)
{
if (nums[j] > nums[i] && m < (j - i))
m = j - i;
}
}
// Return the maximum j-i value
return m;
}
int main()
{
int nums[] = {5, 3, 8, 6, 7};
int n = sizeof(nums) / sizeof(nums[0]);
int m = valCalculator(nums, n);
cout << "The array is: " << endl;
for (size_t i = 0; i < n; i++)
{
cout << nums[i] << " ";
}
cout << endl
<< "The maximum j-i value is: ";
cout << "\n" << m;
return 0;
}
```

**Output**

#### Time Complexity

The time complexity for the given approach is O(n^{2}) as we run two loops to check for the maximum j-i value in the array in cases where arr[j] > arr[i].

#### Space Complexity

The Space Complexity of the above approach is O(1) as no other data structures are used for memory in the described solution.