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

Question

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

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

找到最长的递增子序列：

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

首先了解我在 google 上搜索的操作，我发现了这个函数：

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 个节点。此外，space 的复杂性也很重要，因为我们在函数参数中复制子问题的列表。为了克服这个问题，使用了动态规划。

Answer 2

结果不正确，但至少可以调用函数：

/**
*
* @author lucius
*/
public class LISQuestion {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here

    int[] lis = new int[]{1,2,8,3,6,4,9,5,7,10};//empty array where LIS will be stored

    int[] arr = lis; //sequence where LIS should be searched

    int lisIndex = arr.length-1;

    int max = 10;

    printLis(lis, lisIndex, arr, max);
}

public static void printLis (int [] lis, int lisIndex, int [] arr, int max) {
    if (max == 0) {
        return;
    }
    if(lisIndex < 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);
    }

}

}

实际上Java，您总是需要一个 main 方法作为程序的入口点。

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

How to make a call of this recursive Longest Increasing Subsequence function

java

algorithm

recursion

function

lis

复杂性