Zadanie - maksymalny dystans indeksów.

Mam poniższe zadanie:

A non-empty zero-indexed array A consisting of N integers is given.
A monotonic_pair is a pair of integers (P, Q), such that 0 ≤ P ≤ Q < N and A[P] ≤ A[Q].

The goal is to find the monotonic_pair whose indices are the furthest apart. More precisely, we should maximize the value Q − P. It is sufficient to find only the distance.

For example, consider array A such that:

A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2

There are eleven monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5). The biggest distance is 3, in the pair (1, 4).
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A of N integers, returns the biggest distance within any of the monotonic_pairs.
For example, given:
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
the function should return 3, as explained above.
Assume that:
N is an integer within the range [1..300,000];
each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Tłumaczenie, może nieco niedoskonałe:

Mamy daną niepustą, indeksowaną od zera tablicę tab, zawierającą n liczb całkowitych.
Pewna para_monotoniczna jest parą liczb całkowitych (p, q), takich że 0 <= p <= q < n
oraz tab[p] <= tab[q].
Celem zadania jest znaleźć 1 parę_monotoniczną, w której indeksy składników są najbardziej różne.
Bardziej precyzując, musimy znaleźć parę, która posiada największą różnicę pomiędzy indeksami
p i q (różnica = q - p).
Dla przykładu, rozważmy następującą tablicę tab:
tab[0] = 5
tab[1] = 3
tab[2] = 6
tab[3] = 3
tab[4] = 4
tab[5] = 2
Jest w tablicy tab 11 par_monotonicznych : (0,0),(0,2),(1,1),(1,2),(1,3),(1,4),(2,2),(3,3),(3,4),(4,4),(5,5).
Tutaj największa różnica pomiędzy indeksami pary wynosi 3(w parze (1,4)).
Napisz funkcję:
class Problem { public int rozwiazanie(int[] tab); }
taką, że mając daną tablicę tab zwraca największą wartość różnicy w parze.
Podczas rozwiązywania zadania należy wziąć pod uwagę możliwość, że:
*n jest integerem z zakresu [1...300,000],
*każdy element tablicy tab jest liczbą typu integer z zakresu [1 ... 1000,000,000].

Moje rozwiązanie:

 public class Problem {
	
	public int rozwiazanie(int[] t){
		long start = System.nanoTime();
		int wynik = -987654;
		int[] roznice = new int[t.length];
		
		for(int i = 0; i < t.length; i++){
			for(int j = 0; j < t.length; j++){
				if((i <= j) && (t[j] >= t[i])){
					roznice[i] = j - i;
					//System.out.print(roznice[i] + ", ");
				}
			}
		}
		
		wynik = roznice[0];
		for(int i = 0; i < roznice.length; i++){
			if(wynik < roznice[i]){
				wynik = roznice[i];
			}
		}
		
		long koniec = (System.nanoTime() - start) / 1000000000;
		//System.out.println("Czas wykonania: " + koniec + " sekund");
		return wynik;
	}

Niestety, ten sposób jest za wolny... Przy 300000 indeksów i7 4 rdzenie wysiada. Jak inaczej można rozwiązać takie zadanie?

Mój pomysł tak na szybko z O(nlogn), szybciej już chyba nie będzie bo nie widzę opcji działającej z O(n).
-wrzucamy sobie dane wejściowe do mapy gdzie kluczem jest wartość liczby a wartością jest para (minimalny indeks, maksymalny indeks)

• następnie iterujemy sobie od końca i patrzymy na pary liczb w mapie wyliczając sobie pierwszą różnicę indeksów jako
  różnica_n-1 = mapa[n].maksymalny_indeks - mapa[n-1].minimalny_indeks
  a każdą następną korzystając z poprzedniej na zasadzie:
  różnica_i_1 = różnica_poprzedniego + mapa[i+1].minimalny_indeks - mapa[i].minimalny_indeks [czyli maksymalna różnica między aktualnym elementem a wszystkimi poprzedzającymi]
  różnica_i_2 = mapa[i+1].maksymalny_indeks - mapa[i].minimalny_indeks [czyli różnica między aktualnym elementem a jego sąsiadem]
  i wybieramy z tych 2 większą różnicę.
  I z tych różnic wybieramy sobie różnicę największą dla wszystkich i.

Nie ręczę za to, ale wydaje mi sie że będzie działać ;]

Oryginalne rozwiązanie można przyspieszyć mniej więcej dwukrotnie rezygnując z tablicy różnice i wprowadzając oczywistą zmianę w pętli wewnętrznej

for(int j = i+1; j < tab.length; j++)

Można też odwrócić kierunek poszukiwań, wpierw porównujemy elementy odległe. Poniższy kod jest wolniejszy (2x) w pewnych przypadkach skrajnych (np. tablica ściśle malejąca). Średnio (na losowych danych) jest około 500 razy szybszy.

        int result = 0;
        int distance = tab.length - 1;
        while(distance >= 1 && distance > result)
        {
            for(int i=0;i<tab.length;i++)
            {
                if(i+distance<tab.length && tab[i+distance] >= tab[i])
                {
                    result = distance;
                }
            }
            distance--;
        }
        return result;

Czapki z głów, bogdans. Twój kod działa nawet przy 30 mln tablicy. Ja się na 2 for-ach oparłem o coś ok. 300 tyś.
Jak poniżej:

 import java.util.Random;

public class Problem {
	
	public static long rozwiazanie(int[] tab){
		long roznica = 0;
	
		for(int p = 0; p < tab.length; p++){
			for(int q = 0; q < tab.length; q++){
				if((p <= q) && (tab[p] <= tab[q])){
					int wynik = q - p;
					if(roznica < wynik) roznica = wynik;
				}
			}
		}
		
		return roznica;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] tab = new int[30000];
		for(int i = 0; i < tab.length; i++){
			tab[i] = new Random().nextInt(1000000000);
		}
		System.out.print(Problem.rozwiazanie(tab));

	}

}

Algorytmiki to się muszę jeszcze długo pouczyć ...