ArrayList ordinamento sequenza più lunga

Question

Io sono non chiedere a chiunque di risolvere questo per me, ho solo bisogno di una piccola spinta perché non ho idea terrena su dove cominciare con questo. Tutto quello che so è che dovrei implementare le raccolte in questo e avere un qualche tipo.

Scrivere un metodo longestSortedSequence che restituisce la lunghezza della sequenza ordinata più lunga all'interno di un elenco di numeri interi. Ad esempio, se una variabile denominata lista memorizza la seguente sequenza di valori:

[1, 3, 5, 2, 9, 7, -3, 0, 42, 308, 17] 

allora la chiamata: list.longestSortedSequence() restituirà il valore 4, in quanto è la lunghezza della sequenza più lunga filtrate all'interno di questo elenco (la sequenza -3, 0, 42, 308). Se l'elenco è vuoto, il metodo dovrebbe restituire 0. Si noti che per un elenco non vuoto il metodo restituirà sempre un valore di almeno 1 poiché ogni singolo elemento costituisce una sequenza ordinata.

Assume you are adding to the ArrayIntList class with following fields: 

public class ArrayIntList 
{ 
    private int[] elementData; 
    private int size; 

    // your code goes here 
} 

Answer 1

Avete mai pensato a un ciclo for e in caso contrario istruzioni? spero che questo non lo dia via. pensa un elemento alla volta.

Answer 2

Passa sopra l'array e confronta l'elemento i con l'elemento i+1. Fai un contatore. Mentre i è inferiore a i+1 incrementa il contatore, quando i è maggiore di i+1 reimposta il contatore.

Answer 3

Iterare la matrice e incrementare la variabile contatore se l'elemento successivo elaborato è più grande dell'ultimo.

Se l'elemento successivo è minore, o viene raggiunta la fine dell'array, memorizzare il valore corrente del contatore se grande allora il valore massimo attualmente memorizzato e ripristinare la variabile contatore con 0.

Answer 4

Pseudo codice:

Variable X: first item of list 
Variable Y: length of sequence (initial: 1) 
Variable Z: max length occurred (initial: 0) 
Loop over the list starting from 2nd index 
if item is higher than X 
    set X to item 
    add 1 to Y 
else 
    if Y is higher than Z 
    set Z to Y 
    end if 
    set X to item 
    set Y to 1 
end if 
End-Loop 

Questo metodo riavvierà il contatore ogni volta che la sequenza "si riavvia", ovvero: non è più in ordine. Mentre l'elenco è ordinato, aggiunge solo 1 per ogni elemento che si trova nell'ordine ordinato.

Quando la sequenza smette di essere ordinata, controlla se la sequenza corrente è più lunga della lunghezza di sequenza più lunga finora. Se lo è, hai la tua nuova sequenza più lunga.