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

Question

I'm learning about recursion. I have taken as an example the algorithm LIS (Longest increasing subsequence) which given an array:

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

Find the longest increasing subsequence that would be:

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

To start with an idea of the operation I was searching on google and I found that function:

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

How do I call that function in my example, so that I get the indicated results?

Answer 1

Above code is not for calculating LIS. Its for printing the LIS elements. Also the snippet contains syntax error.

Here is a better recursive solution in Java with explanation.

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));


    }
};

Output

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

Complexity

The corresponding tree due to this recursion is like this -

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

The time complexity is exponential. There will be 2^n - 1 nodes will be generated for a n sized array. Plus the space complexity is significant too as we are copying sub-problem's list in function argument. TO overcome this, dynamic programming is used.