Clever Geek Handbook

Find All Long Ascending Subsequences Given by an Array of Integers - Dynamic Programming

I am learning dynamic programming and I came across this question where I have to print all the longest subsequences. There can be more than one longest subsequence for an array. The program I've tried will only give me one long subsequence, but not the whole long subsequence. How do I get the longest subsequences?

//Initially I create two arrays of the length of the given input array 

public static void LIS(int[] input) {

    String paths[] = new String[input.length];
    int[] size = new int[input.length];

    for(int i=0;i<input.length; i++) {
       paths[i] = input[i];
       size[i] = 1;
    }

    for(i=1; i<input.length ; i++) {

        for(j=i; j< i ; j++) {
            if(input[i] > input[j] && size[i] < size[j] + 1) {
                size[i] =  size[j] +1;
                paths[i] =  paths[j] + input[i] + ""

                if (maxlength < size[i]) {
                    maxlength = size[i];
                }
            }
        }
    }
}

My example input [] = 1,8,10,3,7,12,15

with the above algorithm i get the longest subsequence as 1,8,10,12,15

I should also get 1,3,7,12,15

How can I change the code to get this?

+3


source to share


1 answer


If you want to change this code, you can keep all possible predecessors for any element; from your code:

for(i=1; i<input.length ; i++) {

    for(j=i; j< i ; j++) {
        //if(input[i] > input[j] && size[i] < size[j] + 1) {
        if(input[i] > input[j] && size[i] <= size[j] + 1) {
            size[i] =  size[j] +1;
            //paths[i] =  paths[j] + input[i] + ""
            if (size[i] < size[j] + 1 )
               //empty p[i]
            p[i].push(j);

            if (maxlength < size[i]) {
                maxlength = size[i];
            }
        }
    }
}


and then you will need to reconstruct all possible subsequences

+1


source






More articles:


All Articles