Calculating longest increasing sub-sequence recursively

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

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.

StackExchange Code Review Q#102232, answer score: 8