java来寻找给定整数数组的所有最长递增子序列动态规划

Question

我在学习动态编程&；我遇到了一个问题，我必须打印出所有最长的子序列。给定一个数组，可能有多个最长的子序列。 我尝试的程序只会给我一个最长的子序列，但不是所有最长的子序列。如何获得所有最长的子序列

//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];
                }
            }
        }
    }
}

我的示例输入[]=1,8,10,3,7,12,15

用上述算法得到的最长子序列为1,8,10,12,15

我也应该得到1,3,7,12,15

如何修改代码以获得此信息

Answer 1

如果要修改此代码，可以存储任何元素的所有可能前导代码； 从您的代码：

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];
            }
        }
    }
}

然后你需要恢复所有可能的子序列