12
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ Recursion is not necessary here at all, just because you can doesn't mean you should. Try to solve a few small problems using pen and paper, and then code up the method you used. \$\endgroup\$
    – spyr03
    Aug 29 '15 at 20:07
  • \$\begingroup\$ This may be too insignificant as a separate answer, but identifiers that start with an underscore are reserved in the global scope. Consider using another name. \$\endgroup\$
    – L. F.
    Apr 20 '19 at 3:47
8
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$
  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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ What does a[1:]>a[0] notation mean? \$\endgroup\$
    – max
    Nov 22 '16 at 19:06
  • \$\begingroup\$ longest-increasing subsection is the first array element plus the longest-increasing subsection of all remaining elements that are greater than that first array element. This helped me in understanding the real solution \$\endgroup\$
    – Rohit
    Jan 19 '17 at 15:17
2
\$\begingroup\$

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);
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ I would avoid using namespace std. \$\endgroup\$
    – Null
    Oct 31 '18 at 16:00
  • \$\begingroup\$ does lcs() in your code represent _lis of the OPs code? \$\endgroup\$ Oct 31 '18 at 16:04
  • \$\begingroup\$ yes...lcs represents _lis \$\endgroup\$
    – Tokumei
    Oct 31 '18 at 18:35
  • \$\begingroup\$ @Null I would also avoid them in case I am writing a big program . This is a very basic program and I think its not that bad to include namespace here. \$\endgroup\$
    – Tokumei
    Oct 31 '18 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.