Recursive algorithm to select ascending noncontiguous numbers from a list

Question

I need to write a function which finds the longest, not necessarily contiguous, ascending sub-sequence in a list of numbers. The function needs to be recursive.

I have a problem with my algorithm and I cannot figure out how to fix it. Here's an example starting list:

[88, 1, 22, 3, 34, 6, 54, 9, 19]

The correct result is:

[1, 3, 6, 9, 19]

and I want to print on the screen the length of this sub-sequence, in this case, 5.

My function:

int subseires(int arraysub[], int small, int i, int j, int coun){
    if( i==size ) return 0;

    if( arraysub[i]>arraysub[j] )
        subseires(arraysub, small, i+1, j+1, coun);

    if( arraysub[i]<arraysub[j] )
        subseires(arraysub, small, i, j+1, coun+1);

    return coun;
}

Can anyone help by pointing out the problems with my procedure?

Answer 1

Your algorithm is probablly wrong.

What you need to do is for each member of the aray-if you can select it(it's not less than the previous one you have selected) then check two options recursivelly: to select it or not to select it. This way you go until the end of the array and return the total length. In the end you print the longest length.

Try to implement this algorithm in a C function.

Answer 2

So you only need to print the length of the list, not the list itself? That helps, because it simplifies memory management (which is an issue for c).

This is really just a glorified search. At each point you need to know (1) the current value (if any); (2) the current length (if any); (3) the position in the list; (4) the largest length known. Using a length of zero helps track when you have no current value (so you don't need a "magic" initial value). The return value should be the largest length.

On each recursion you can either skip the current number or include it in the list (but only if it is less than the current value).

so the code is just:

#include <stdio.h>

int max(int a, int b) {
  return a > b ? a : b;
}

int find(int* data, int total_length, int offset, int previous,
         int run_length, int max_length) {
  // update max length if it has improved                                       
  if (run_length > max_length) max_length = run_length;
  // if we are at the end, return max                                           
  if (offset == total_length) return max_length;
  // if the current value is too small, we cannot include it                    
  if (run_length && data[offset] <= previous)
    return find(data, total_length, offset+1, previous, run_length, max_length);
  // otherwise, we want the best of either including it or not                  
  return max(
    // try including it                                                         
    find(data, total_length, offset+1, data[offset], run_length+1, max_length),
    // try excluding it                                                          
    find(data, total_length, offset+1, previous, run_length, max_length));
}

// test                                                                         
int main(int argc, char *argv) {
  int data[] = { 88, 1, 22, 3, 34, 6, 54, 9, 19 };

  printf("%d\n", find(data, 9, 0, 0, 0, 0));
  return 0;
}

obviously this is terrible c code (not because I didn't use array initialization, which someone "kindly" fixed (although they didn't bother to vote this answer - I guess they think I am motivated to post here by learning from their deep knowledge of C syntax) but because it uses the call stack where it would be more efficient to use a separate memory structure).

(also, I have to say, writing something like this is much easier as a recursive function than as doing it in a loop, because you just write down what you want to happen - if you had a loop then you would need to worry about changing values and resetting them and all that mess. The problem is that it abuses the stack horribly).