Calculating longest increasing sub-sequence recursively

Question

I have trouble understanding recursion, so I'm trying to implement algorithms using it. I wrote this code that calculates the length of the longest increasing sub-sequence. How can I improve this?

int _lis(int arr[], int n){
  if(n==0) return 1;

  int m=1, temp; 
  for(int i=0; i<n; i++){
    if(arr[i]<arr[n]){
        temp= 1 + _lis(arr, i);
        if(temp > m)
            m=temp;    //   m = max(m, 1 + _lis(arr, i));
    }
  }
  return m;
}

int LIS(int arr[], int n){
  int temp, m=0;

  for(int i=0; i<n; i++){
    temp = _lis(arr, i);
    if(temp>m)
        m= temp;
  }
  return m;
}

Examples:

• {3, 1, 2, 5, 1, 6} returns 4. (LIS : 1, 2, 5, 6)
• { 10, 22, 9, 33, 21, 50, 41, 60 } returns 5. (LIS : 10, 22, 33, 50, 60)

Answer 1

Time complexity

Your recursive solution works, but the time complexity is not optimal. In the worst case where the array is sorted in increasing order, the time complexity appears to be \$O(n!)\$, because for each length you recurse on every length less than it.

What you need to do is to avoid recomputing solutions you've already found. If you used some kind of memoization (i.e storing answers you've already found), you should be able to reduce the problem to time complexity \$O(n^2)\$. For example, if you already computed _lis(arr, 5), then the next time you need to compute it, you should be able to just reuse the previous answer instead of recomputing it the recursive way. All you would need to do is have an array of size n to store your results as you compute them.

Answer 2

  int m=1, temp;

You declare temp before the loop, but you never use it after an iteration. So you could just say

        int temp = 1 + _lis(arr, i);

in the loop. This brings declaration and use closer together. It also signals more clearly that the value is only used in a single iteration.

Answer 3

Recursive Definition

Recursive algorithms gain efficiency by reducing the scope of the problem until the solution is trivial. Thus, we need to define the problem in terms of sub-array. With that in mind, we can define longest-increasing subsection as the first array element plus the longest-increasing subsection of all remaining elements that are greater than that first array element.

In pseudo-code: LIS(a) = a[0] + LIS(a[1:]>a[0])

Now that we have that definition, we need a terminal state. Since the last subarray in this definition will be an empty array, that is the terminal state. if(a == []): return 0 will be the end of the recursive chain.

Implementation Details

Since c does not have slices like Python, we can traverse with a pointer from the head of the remaining array. We use the address of the last element to flag the end of the traversal.

int _lis(int *arr, int *end){
    if(arr == NULL || end == NULL) return 0; //input validation

    //arr holds the last element of the lis, so we need a traversal pointer
    int *traverse;  
    traverse = arr;

    //Find the next array element greater than the current lis
    while(*traverse <= *arr && traverse != end)
    {   traverse++; }

    if(traverse == end) //traversal reached end of the array
    {   
        return (*traverse > *arr)? 1: 0;  //Check if the last element is in the lis
    }
    return 1+_lis(traverse, end) //look at the rest of the list
}

Now you can re-write your input function LIS to give a clean face to the user:

LIS(int arr[], int arr_len){
    if(len == 0) return 0;

    int max = 0, temp;
    for(int i = 0; i < arr_len; ++i){
        temp = _lis(&(arr[i]), &(arr[arr_len-1]));
        max = (temp > max)?temp: max;
    }
}

This way, you traverse the array at most once for each starting point. It's still O(n^2), but that's much better than O(n!) and it shows the recursive definition much more clearly.

Answer 4

You are just missing one thing . Try input {10,22,9,33,21,51,41,60,80,5} .

You are just assuming that the last element is always included in the longest increasing subsequence . So in the loop you should include that if arr[i]>arr[n] then temp=_lis(arr,i) , and then compare temp with m . The rest is fine, I suppose. Also , it would be better for CPU if you just keep on storing the calculated results so that it won't recalculate it.

#include<iostream>
using namespace std;
int a[]={10, 22, 9, 33, 21, 50, 41, 60, 80, 5};
int lcs(int len){
    if(len==0) return 1;
    int m=1;
        int temp;
    for(int i=0;i<len;i++){
        if(a[i]<a[len]) temp=1+lcs(i);
        else temp=lcs(i);
        if(temp>m) m=temp;
        }
    return m;
}
int main(){
    cout<<lcs(9);
}