Maior subsequência

Boa noite a todos do GUJ.

Bom pessoal, minha dúvida é a seguinte, dado um conjunto de valores em um Array eu gostaria de encontrar a maior subsequencia não contigua desse meu ArrayList.

Tenho o seguinte código abaixo, e se vocês o executarem notarão que a maior subquencia é 3 4 8 9.
Então eu gostaria de saber o que que tenho que alterar em meu código para mostrar isso ao usuário final.
Tentei add em um outro ArrayList mas não deu certo.

Alguém poderia me dar uma dica?
Desde de já obrigado pela ajuda de todos.

import java.util.ArrayList;

public class Ex_4 {
    public static void main(String[] args) {
        int[] vet = {7,6,10,3,4,1,8,9,5,2};
        ArrayList<Integer> array = new ArrayList<Integer>();
        ArrayList<Integer> newArray = new ArrayList<Integer>();
        //ArrayList<Integer> finalArray = new ArrayList<Integer>();

        for (int i = 0; i < vet.length; i++) {
            array.add(vet[i]);
        }

        for (int i = 0; i < array.size()+i; i++) {
            int p1 = array.get(0);
            //System.out.println(array.size() + " " + p1);
            for (int j = 0; j < array.size(); j++) {
                //array.add(array.get(0));
                //System.out.println(p1);
                if(p1 <= array.get(j)){
                    p1 = array.get(j);
                    //newArray.add(p1);
                    System.out.print(p1 + " ");
                }
            }
            
            System.out.println();
            //System.out.println(newArray);
            array.remove(array.get(0));
        }
    }
}

1 Resposta

jeovane.reges 22 de out. de 2011

Conseguir da seguinte forma abaixo.
Mas, caso alguem tenha uma outra sugestão, é bem vinda.

import java.util.ArrayList;

public class Ex_4 {
    public static void main(String[] args) {
        int[] vet = {7,6,10,3,4,1,8,9,5,2};
        ArrayList<Integer> array = new ArrayList<Integer>();
        ArrayList<Integer> newArray = new ArrayList<Integer>();
        ArrayList<Integer> finalArray = new ArrayList<Integer>();

        for (int i = 0; i < vet.length; i++) {
            array.add(vet[i]);
        }

        System.out.println("Sequência: " + array);

        for (int i = 0; i < array.size()+i; i++) {
            int p1 = array.get(0);
            //System.out.println(array.size() + " " + p1);
            for (int j = 0; j < array.size(); j++) {
                //array.add(array.get(0));
                //System.out.println(p1);
                if(p1 <= array.get(j)){
                    p1 = array.get(j);
                    newArray.add(p1);
                    //System.out.print(p1 + " ");
                }
            }
            
            //finalArray.addAll(newArray);
            if (finalArray.size() < newArray.size()) {
                //System.out.println("1: " + finalArray.size());
                //System.out.println("2: " + newArray.size());
                finalArray.clear();
                finalArray.addAll(newArray);
            }
            
            //System.out.println("newArray: " + newArray);
            //System.out.println("finalArray: " + finalArray);

            //System.out.println("finalArray: " + finalArray.size());
            //System.out.println("newArray: " + newArray.size());

            newArray.clear();
            array.remove(array.get(0));
        }
        System.out.println("Maior Subsequência: " + finalArray);
    }
}

1 Resposta

Topicos relacionados