ho fatto una cosa del genere:
codice:
public int maxPrimoRelativo(int[] a) {                
        int index = 0;        
        for (int i = a.length -1; i >= 1; i--) {            
            index = i;
            int divs = 0;
            for (int j = i -1 ; j >= 0 && divs == 0; j--) {                                
                divs += (a[i] % a[j] == 0 ? 1 : 0);                
            }
            if (divs == 0) {
                break;
            }
        }
        return a[index];
    }
dove "a" è ordinato in modo crescente.

Come funziona:
- index è un "cursore" che tiene traccia dell'elemento che sto analizzando
- divs tiene invece traccia del numero di sottomultipli trovati fino a quel momento (ovviamente è inizializzata a zero)
- il ciclo for interno parte da una posizione "in meno" rispetto al ciclo esterno (ovvio - altrimenti troveresti subito un divisore, ossia l'elemento stesso)
- se nel ciclo interno viene trovato un divisore/sottomultiplo, aumento il computo dei sottomultipli.
- l'if verifica se i sottomultipli siano zero, se fosse così, esce dal ciclo esterno e possiamo ritornare l'elemento all'indice in analisi.