finding the largest ascending subsequence..

**~~transgalactic2~~** · 01-17-2009

you are correct

**fanan** · 01-17-2009

Originally Posted by root4

my attempt:

Code:

#include <stdio.h>
int foo(int a[],int size,int i,int j) {
  // pre-condition: j>i
  if(j>=size) return 1;
  int r1=foo(a,size,j,j+1)+(a[j]>a[i]);
  int r2=foo(a,size,i,j+1);
  return (r1>r2?r1:r2);
}
int main() {
  int a[]={45,1,21,3,33,6,53,9,18};
  printf("%u\n",foo(a,sizeof(a)/sizeof(int),0,1)); // 5
  int b[]={-3,-2,-1,4,8,6,53,9,18};
  printf("%u\n",foo(b,sizeof(b)/sizeof(int),0,1)); // 7
  int c[]={1,2,3,4,5,6,7,8,9,10};
  printf("%u\n",foo(c,sizeof(c)/sizeof(int),0,1)); // 10
  return 0
}

man you are a genious!!

**itCbitC** · 01-17-2009

Here's my 2c though IMO the one posted by root4 is the best - short and sweet.

Code:

#include <stdio.h>

int mxstart(int a[],int i,int j,int o,int l,int c,int p,int v)
{
    if (i <= (l-1)) {
        if (j >= i) {
            if (a[j] <= a[o]) {
                if (a[j] >= a[i])
                    return mxstart(a,i,j-1,j,l,c+1,p,v);
                else
                    return mxstart(a,i,j-1,j-1,l,c,p,v);
            } else
                return mxstart(a,i,j-1,o,l,c,p,v);
        }
        if (c >= p)
            p = c;
        else
            c = p;

        return mxstart(a,i+1,l-1,l-1,l,0,p,v);
    }
    else {
        if (v < l)
            return mxstart(a,v+1,l-1,l-1,l,0,p,v+1);
        else
            return (c >= p ? c : p);
    }
}

int main()
{
    int c;
    int a[]={45,1,21,3,33,6,53,9,18};
    int l = (sizeof a / sizeof a[0]);

    c = mxstart(a,0,l-1,l-1,l,0,0,0);
    printf("longest ascending subsequence is %d\n", c);
    return 0;
}

**arpsmack** · 01-17-2009

The function posted by root4 certainly is short and sweet, but it doesn't seem to work for all cases.

For example:

Code:

{3, 4, 1, 2} and {2, 4, 1, 3}

Both have a longest increasing subsequence of length 2. However, foo() returns 3 for both of them. Hopefully this is just a simple off-by-one error.

mxstart() has a problem with these cases:

Code:

{2, 4, 1, 3}: should be 2, mxstart() says 3
{1, 3, 4, 2}: should be 3, mxstart() says 2

and dwks' longest_ascending() returns all sorts of incorrect results, even for trivial cases:

Code:

The answer on the left is what longest_ascending() returned.
In parentheses is the correct answer.
{4, 3, 2, 1}: 2 (1)
{4, 1, 3, 2}: 3 (2)
{4, 2, 3, 1}: 3 (2)
{3, 4, 2, 1}: 3 (2)
{3, 4, 1, 2}: 3 (2)
{2, 4, 1, 3}: 3 (2)
{2, 4, 3, 1}: 3 (2)
{1, 4, 3, 2}: 3 (2)
{3, 1, 4, 2}: 3 (2)
{3, 2, 4, 1}: 3 (2)
{2, 3, 4, 1}: 4 (3)
{1, 3, 4, 2}: 4 (3)
{2, 1, 4, 3}: 3 (2)
{1, 2, 4, 3}: 4 (3)

These were tested against a non-recursive reference implementation (which I assumed to be correct), and manually verified the cases that didn't match. The reference implementation in C can be found here: http://www.algorithmist.com/index.ph..._Subsequence.c

This is what I came up with (but that isn't really fair because I've discussed this problem in school before). Its similar to what root4 did.

The longest ascending subsequence (LAS) of array A is either:

A[0] + the LAS of the rest of the array
The LAS of the rest of the array without A[0]

HOWEVER, there is an additional constraint. If the LAS is A[0] + LAS(rest of array), then A[0] must be less than the smallest element in LAS(rest of array). Also I take advantage of the fact that LAS(A) == LAS(A) with the minimum element in the sequence greater than INT_MIN. Hopefully INT_MIN doesn't appear in the array!

Code:

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

int las_greater_than(int x, int *a, int lo, int count)
{
   if (lo >= count)
      return 0;
   
   int max = las_greater_than(x, a, lo + 1, count);
   
   if (a[lo] > x)
      max = maximum(max, las_greater_than(a[lo], a, lo+1, count) + 1);
   
   return max;
}

int las(int *a, int count)
{
   return las_greater_than(INT_MIN, a, 0, count);
}

Once again though, if you think this is amazing or something, I DIDN'T INVENT THIS ALGORITHM. I learned it through discussions in a class I took.

**kavka3** · 01-18-2009

root4 !!!

Code:

#include <stdio.h>
int foo(int a[],int size,int i,int j) {
  // pre-condition: j>i
  if(j>=size) return 1;
  int r1=foo(a,size,j,j+1)+(a[j]>a[i]);
  int r2=foo(a,size,i,j+1);
  return (r1>r2?r1:r2);
}
int main() {
  int a[]={45,1,21,3,33,6,53,9,18};
  printf("%u\n",foo(a,sizeof(a)/sizeof(int),0,1)); // 5
  int b[]={-3,-2,-1,4,8,6,53,9,18};
  printf("%u\n",foo(b,sizeof(b)/sizeof(int),0,1)); // 7
  int c[]={1,2,3,4,5,6,7,8,9,10};
  printf("%u\n",foo(c,sizeof(c)/sizeof(int),0,1)); // 10
  return 0
}

for this input -- 7 8 2 1 7 i get 3
but i should get 2

**root4** · 01-18-2009

I said it was an attempt, nothing more

While there is no formal proof, it doesn't have any value.

here's the patch, the previous version was indeed wrong (merged two branches that should not), the new version is less simple but probably more correct:

Code:

int foo(int a[],int size,int new,int i,int j) {
  if(j>=size) return 0;
  int r1=a[j]>a[i]?foo(a,size,0,j,j+1)+1+new:0;
  int r2=new?foo(a,size,1,j,j+1):0;
  int r3=foo(a,size,new,i,j+1);
  return r1>r2?(r1>r3?r1:r3):(r2>r3?r2:r3); // max(r1,r2,r3);
}
int main() {
  int a[]={...};
  printf("%u\n",foo(a,sizeof(a)/sizeof(int),1,0,1));
  return 0;
}

arpsmack version is more attractive. (and seems proved).

**dwks** · 01-18-2009

Yeah, my bad. I meant

Code:

int longest = 0;

where I put

Code:

int longest = 1;

Sigh.

[edit] I don't claim that my new solution is completely correct, but it does at least pass those tests it failed earlier. (Sorry for my hackish perl script...)

Code:

$ perl -ne '/.(\d), (\d), (\d), (\d)......(\d)/; $o = `./long0 $1 $2 $3 $4 | sed 's/[^0-9]//g'`; chomp $o; print "$o ($5)\n"' in
1 (1)
2 (2)
2 (2)
2 (2)
2 (2)
2 (2)
2 (2)
2 (2)
2 (2)
2 (2)
3 (3)
3 (3)
2 (2)
3 (3)

[/edit]

**~~transgalactic2~~** · 01-19-2009

thanks

**arpsmack** · 01-19-2009

root4:

Your solution now gets the correct answer for every input except a strictly decreasing sequence. It seems like a very minor problem. For example:

Code:

{2, 1}: should be 1, foo() says 0
{3, 2, 1} should be 1, foo() says 0
etc...

dwks:

longest_ascending() now works for all inputs I throw at it

. And what a minor fix that was!

**itCbitC** · 01-19-2009

The earlier one was indeed wrong and in the spirit of updating here's my latest.

Code:

#include <stdio.h>

int mxstart(int a[],int i,int j,int o,int l,int c,int p,int v)
{
    if (i <= (l-1)) {
        if (o >= i) {
            if (j >= i) {
                if (a[i] <= a[o]) {
                    if ((a[j] <= a[v]) && (a[j] >= a[i]))
                        return mxstart(a,i,j-1,o,l,c+1,p,j);
                    else
                        return mxstart(a,i,j-1,o,l,c,p,v); 
                } else
                    return mxstart(a,i,o-1,o-1,l,0,p,o-1);
            } else {
                if (c >= p)
                    p = c;
                else
                    c = p;
                return (c >= (l-i) ? c : mxstart(a,i,o-1,o-1,l,0,p,o-1));
            }
        } else
            return mxstart(a,i+1,l-1,l-1,l,0,p,l-1);
    } else
        return (c >= p ? c : p);
}

int main()
{
    int c;
    int a[]={45,1,21,3,33,6,53,9,18};
    int l = (sizeof a / sizeof a[0]);

    c = mxstart(a,0,l-1,l-1,l,0,0,l-1); 
    printf("longest ascending subsequence is %d\n", c);
}

**root4** · 01-19-2009

Your solution now gets the correct answer for every input except a strictly decreasing sequence

Good catch. Indeed the function returns 0 if there is not at least a pair of ascending numbers (i.e. a result of 2), changing the final result in something like max(r1,r2,r3,new?1:0) should do the trick but there surely a way to make it more elegant. I won't spend more time on it, several solutions were proposed or hints for solutions, there's enough to play for the OP or the ones interested...

**arpsmack** · 01-20-2009

Originally Posted by itCbitC

The earlier one was indeed wrong and in the spirit of updating here's my latest.

I hate to be the bearer of bad news, but try one of these inputs:

Code:

{1, 3, 4, 2, 5}: mxstart() says 3, should be 4
{1, 3, 5, 4, 2, 6}: mxstart() says 3, should be 4
{4, 1, 3, 5, 2, 6}: mxstart() says 3, should be 4
{1, 3, 4, 5, 2, 6}: mxstart() says 4, should be 5
{2, 1, 4, 5, 3, 6}: mxstart() says 3, should be 4
{1, 2, 4, 5, 3, 6}: mxstart() says 4, should be 5
etc...

By the way, this is the code I'm using to check your solutions. Just fill in YOUR_FUNC() with the details of however your function works. Run the program on the commandline passing it a number (1 - 12) and it will check all permutations of an increasing sequence of that size.

I.E. - ./a.out 3 will check {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, etc... (in no particular order)

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int lcs( int* a, int N ) {
   int *best, *prev, i, j, max = 0;
   best = (int*) malloc ( sizeof( int ) * N );
   prev = (int*) malloc ( sizeof( int ) * N );
 
   for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;
 
   for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
         if ( a[i] > a[j] && best[i] < best[j] + 1 )
            best[i] = best[j] + 1, prev[i] = j;  // prev[] is for backtracking the subsequence
 
   for ( i = 0; i < N; i++ )
      if ( max < best[i] )
         max = best[i];
 
   free( best );
   free( prev );
 
   return max;
}

void swap(int *a, int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}

void permute(int k, int *s, int count)
{
   int j;
   for (j = 2; j <= count; j++)
   {
      k /= (j-1);
      swap(&s[k%j], &s[j-1]);
   }
}

void print_array(int *a, int size)
{
   int i;
   
   printf("{%d", a[0]);
   for (i = 1; i < size; i++)
      printf(", %d", a[i]);
   printf("}");
}

int fact(int n)
{
   int res = n;
   while (--n > 1)
      res *= n;
   return res;
}

int YOUR_FUNC(int *a, int count)
{
   ...
}

int main(int argc, char **argv)
{
   if (argc < 2) return 0;
   
   int count = atoi(argv[1]);
   
   if (count < 1 || count > 12) return 1;

   int size = count * sizeof(int);
   
   int *inorder = malloc(size);
   int *a = malloc(size);
   
   int n, result, reference;
   
   for (n = 0; n < count; n++)
      inorder[n] = n+1;
   
   for (n = 0; n < fact(count); n++)
   {
      memcpy(a, inorder, size);
      permute(n, a, count);
      
      result = YOUR_FUNC(a, count);
      reference = lcs(a, count);
      
      if (result != reference)
      {
         print_array(a, count);
         printf(": you said %d, should be %d\n", result, reference);
      }
   }

   printf("Done.\n");
   
   return 0;
}

If no errors are printed using inputs 1 - 6 or so, I'd say your answer is probably correct.

**gil_savir** · 01-20-2009

Thanks guys. That really helps understanding my mistake. I was working on the same exercise and got to a code similar to dwks' code. I had a small flaw, which was very difficult to trace.

BTW, the inline code versions suggested here might be beautiful in its compactness. Yet these do not contribute anything for understanding them.

debugging a recursive function with all its self calls is a damn difficult! If anyone can recommend a debugger which shows clearly calls tree with watch for each node in the tree, I'll appreciate it.

Thanks

**matsp** · 01-20-2009

Originally Posted by gil_savir

debugging a recursive function with all its self calls is a damn difficult! If anyone can recommend a debugger which shows clearly calls tree with watch for each node in the tree, I'll appreciate it.

Thanks

Yes, that's ANOTHER good reason to not use recursion. But Visual Studio and gdb, which I think are among the most used debuggers, will show your call-stack, including recursion.

--
Mats

**gil_savir** · 01-20-2009

Originally Posted by matsp

... will show your call-stack, including recursion.
Mats

Most debuggers (also the one on Eclipse) show call-STACK. However, I would like to see a call-TREE. In some recursive functions, the call-stack is not enough for understanding which call is the parent/child of which call on the stack.