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?

this piece of code contains few syntax errors. Try submitting a compilable version first. — freedev
In Java, there is a difference between lower and upper case letters. So printLis is not the same as PrintLis, for example. And if is not the same as If. — RealSkeptic
Do you know Java ? If yes then using this method in a simple java program shouldn't be a problem. Else try to find a sample code for this algo in the language your are familiar with. In case you are not familiar with any language try learning one as you will need some platform to try your algos. — techprat

Kaidul Kaidul · Accepted Answer · 2017-03-26T10:23:19

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.

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

2 Answers

Complexity