java - 如何调用此递归最长递增子序列函数

Question

我正在学习递归。我以给定数组的算法 LIS(最长递增子序列)为例:

1,2,8,3,6,4,9,5,7,10

找到最长的递增子序列:

1,2,3,4,5,7,10

从我在谷歌上搜索的操作的想法开始，我发现了这个功能:

public static void printLis (int [] lis, int lisIndex, int [] arr, int max) {
    if (max == 0) {
        return;
    }
    if (lis [lisIndex] == max) {
        printLis (lis, lisIndex-1, arr, max-1);
        System.out.print (arr [lisIndex] + "");
    } else {
        printLis (lis, lisIndex-1, arr, max);
    }
}

如何在我的示例中调用该函数，以便获得指示的结果？

Answer 1

以上代码不用于计算 LIS。它用于打印 LIS 元素。该代码段还包含语法错误。

这是一个更好的 Java 递归解决方案，并附有解释。

class LIS {

    static int max_lis_length = 0; // stores the final LIS
    static List<Integer> maxArray = new ArrayList<>();

    // Recursive implementation for calculating the LIS
    static List<Integer> _lis(int arr[], int indx)
    {
        // base case
        if (indx == 0) {
            max_lis_length = 1;
            return new ArrayList<>(Arrays.asList(arr[indx]));
        }

        int current_lis_length = 1;
        List<Integer> currList = new ArrayList<>();
        for (int i=0; i< indx; i++)
        {
            // Recursively calculate the length of the LIS ending at arr[i]
            List<Integer> subproblemList = _lis(arr, i);
            int subproblem_lis_length = subproblemList.size();

            // Check if appending arr[indx] to the LIS ending at arr[i] gives us an LIS ending at 
            // arr[indx] which is longer than the previously
            // calculated LIS ending at arr[indx]
            if (arr[i] < arr[indx] && current_lis_length < (1 + subproblem_lis_length)) {
                current_lis_length = 1 + subproblem_lis_length;
                currList = subproblemList;
            }
        }
        currList.add(arr[indx]);

        // Check if currently calculated LIS ending at
        // arr[n-1] is longer than the previously calculated
        // LIS and update max_lis_length accordingly
        if (max_lis_length < current_lis_length) {
            max_lis_length = current_lis_length;
            maxArray = currList;
        }

        return currList;
    }

    // The wrapper function for _lis()
    static int lis(int arr[], int n)
    {    
        // max_lis_length is declared static above 
        // so that it can maintain its value
        // between the recursive calls of _lis()
        List<Integer> r = _lis( arr, n );
        System.out.println(r);

        return max_lis_length;
    }

    // Driver program to test the functions above
    public static void main(String args[]) {        
        int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
        int n = arr.length;
        System.out.println(lis( arr, n - 1));


    }
};

输出

[10, 22, 33, 50, 60]
5

复杂性

由于这个递归对应的树是这样的-

              lis(4)
        /        |     \
      lis(3)    lis(2)   lis(1)
     /   \        /
   lis(2) lis(1) lis(1)
   /
lis(1)

时间复杂度是指数。将为 n 大小的数组生成 2^n - 1 个节点。此外，空间复杂度也很重要，因为我们在函数参数中复制子问题列表。为了克服这个问题，使用了动态规划。