Maximum j - i Such That a[j] > a[i]

Given an array a, find the maximum of j - i over all pairs with i < j and a[i] < a[j]. Return OptionalInt.empty() if no such pair exists (the array never increases). OptionalInt is a container that holds either one int or nothing.

Example

Text

Input:  [34, 8, 10, 3, 2, 80, 30, 33, 1]
Output: 6   (i = 1, j = 7: 8 < 33)

Input:  [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]
Output: 8   (i = 0, j = 8: 9 < 18)

Input:  [6, 5, 4, 3, 2, 1]
Output: empty

Brute force: check every pair

For each i, scan j from the right end towards i. The first a[j] > a[i] found is the farthest one for that i.

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt maxIndexDiff(int[] a) {
        int best = -1; // -1 means no pair found yet; real gaps are at least 1
        for (int i = 0; i < a.length; i++) {
            for (int j = a.length - 1; j > i; j--) {
                if (a[j] > a[i]) {
                    best = Math.max(best, j - i);
                    break;
                }
            }
        }
        return best < 0 ? OptionalInt.empty() : OptionalInt.of(best);
    }

    public static void main(String[] args) {
        System.out.println(maxIndexDiff(new int[]{34, 8, 10, 3, 2, 80, 30, 33, 1}));
        System.out.println(maxIndexDiff(new int[]{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}));
        System.out.println(maxIndexDiff(new int[]{6, 5, 4, 3, 2, 1}));
    }
}

Output

OptionalInt[6]
OptionalInt[8]
OptionalInt.empty

Time: O(n²). Space: O(1).

The variable best starts at -1 as an internal marker. A real gap j - i is at least 1, so -1 cannot be confused with an answer, and the method converts it to OptionalInt.empty() at the end.

Optimal: prefix minimums and suffix maximums

A good start i has a small value, and nothing further left is smaller. A good end j has a large value, and nothing further right is larger. Precompute:

leftMin[i]: the minimum of a[0..=i]
rightMax[j]: the maximum of a[j..]

Both arrays are non-increasing from left to right. Walk them with two pointers starting at 0. If leftMin[i] < rightMax[j], some start at or before i and some end at or after j form a valid pair at least j - i apart, so record j - i and try a wider gap by moving j. Otherwise, move i to find a smaller start.

index	0	1	2	3	4	5	6	7	8
a	34	8	10	3	2	80	30	33	1
leftMin	34	8	8	3	2	2	2	2	1
rightMax	80	80	80	80	80	80	33	33	1

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt maxIndexDiff(int[] a) {
        int n = a.length;
        if (n == 0) {
            return OptionalInt.empty();
        }
        int[] leftMin = a.clone();
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], a[i]);
        }
        int[] rightMax = a.clone();
        for (int j = n - 2; j >= 0; j--) {
            rightMax[j] = Math.max(rightMax[j + 1], a[j]);
        }

        int i = 0, j = 0, best = -1;
        while (i < n && j < n) {
            if (leftMin[i] < rightMax[j]) {
                if (j > i) {
                    best = Math.max(best, j - i);
                }
                j++;
            } else {
                i++;
            }
        }
        return best < 0 ? OptionalInt.empty() : OptionalInt.of(best);
    }

    public static void main(String[] args) {
        System.out.println(maxIndexDiff(new int[]{34, 8, 10, 3, 2, 80, 30, 33, 1}));
        System.out.println(maxIndexDiff(new int[]{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}));
        System.out.println(maxIndexDiff(new int[]{6, 5, 4, 3, 2, 1}));
        System.out.println(maxIndexDiff(new int[]{3, 1, 2}) + " " + maxIndexDiff(new int[]{2, 1}));
    }
}

Output

OptionalInt[6]
OptionalInt[8]
OptionalInt.empty
OptionalInt[1] OptionalInt.empty

Time: O(n): each pointer only moves forward. Space: O(n) for the two arrays.

Why a recorded gap is real: leftMin[i] is the value at some index i' <= i, and rightMax[j] is the value at some index j' >= j. With j > i, that gives i' < j', a[i'] < a[j'], and j' - i' >= j - i. The j > i check matters: i can move past j (in [3, 1, 2], i reaches 1 while j is still 0), and j - i would then be negative.

Edge cases

Strictly decreasing array: empty result.
Equal values: do not count, because the comparison is strict.
Empty or single element: empty result.