java - To find all longest increasing subsequences given an array of integers - Dynamic Programming -

java - To find all longest increasing subsequences given an array of integers - Dynamic Programming -

i'm studying dynamic programing & came across question in have print out longest subsequences. there more 1 longest subsequence given array. programme tried give me 1 longest subsequence not longest subsequence. how longest subsequences?

//initially create 2 arrays of length of 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< ; 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 illustration input[] = 1,8,10,3,7,12,15

with above algorithm longest subsequence 1,8,10,12,15

i should 1,3,7,12,15

how can modify code this?

if want modify code may store possible predecessors element; code:

for(i=1; i<input.length ; i++) { for(j=i; j< ; 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 need restore possible subsequences

java algorithm data-structures dynamic-programming