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

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