Visto che l'operatore [] degli array accetta un int, puoi allocare un array grande max come il massimo numero rappresentabile da un int (Integer.MAX_VALUE). Cmq dicono che alcune JVM usano fino a 16 byte della memoria allocata di un array come spazio riservato (2 byte vengono usati anche per salvarsi la lunghezza dell'array allocato), quindi alla fine alloca Integer.MAX_VALUE - 8 per sicurezza

Poi ti da errore di memoria perchè la memoria heap per quell'applicazione e' poca.
Puoi aumentarla passando -XmsN (specificando in N il num di byte) alla riga di comando di esecuzione del programma (fai java --help nella console per vedere precisamente quale parametro passare)

Poi allocando un array di Integer allochi un array di puntatori quindi non a 32 ma a 64 bit (4byte).....
usa
codice:
int[] array = new int[Integer.MAX_VALUE - 8];
per allocare un array di int a 32 bit

Per calcolare il tempo in modo piu' preciso usa System.nanoTime()