finding the largest ascending subsequence..

**~~transgalactic2~~** · 01-14-2009

i swear my VS shows 4 while codeblock shows 5

and i did rebuild on VS2005 for five times
??

**fanan** · 01-15-2009

where you from trans?

**TriTon** · 01-16-2009

mkruk, your function is nice, but it doesn't work with negative numbers,
or maybe that's just the way it's supposed to be?

good work anyway.

**~~transgalactic2~~** · 01-16-2009

why it doesnt work on this example of negative numbers??
it shows 4 instead of 6

Code:

#include <stdio.h>
int max_seq(int *arr, int i, int last, int len);
int main()
{

        int i[] = { -3, -2, -1, 4, 8, 6, 53, 9, 18};
        printf("%d is the longest sequence in i\n", max_seq(i, 0, 0, 9));

    return 0;
}

int max_seq(int *arr, int i, int last, int len)
{
        int eval,eval2;
        if(i > len)
                return(0);
         eval = (i == 0 ? max_seq(arr+1, 0, 0, len-1) : 0);
         eval2 = max_seq(arr, i+1, (arr[i] > last ? arr[i] : last), len) + (arr[i] >= last ? 1 : 0);
        return(eval > eval2 ? eval : eval2);
}

**dwks** · 01-16-2009

Just a note: I think it should show 7, because here is a valid subsequence:

Code:

-3, -2, -1, 4, 6, 9, 18

That's seven numbers.

And, actually, that code you just posted prints 3 for me.

Unfortunately, I have no time to debug.

**~~transgalactic2~~** · 01-16-2009

it on the ascending order
after 4 the next member must be 8

**~~transgalactic2~~** · 01-16-2009

why its not working?

**~~transgalactic2~~** · 01-16-2009

this is the translated version:
i traced it for this simple case
and i got twice arr+1
i get out of bounds
??

Code:

#include <stdio.h>
int max_seq(int *arr, int i, int last, int len);
int main()
{

      int i[] = { -3,-2};
	printf("%d is the longest sequence in i\n", max_seq(i, 0, 0, 2));

    return 0;
}

int max_seq(int *arr, int i, int last, int len)
{
    int nSecondIf;
    int nFirstIf;
        int eval,eval2;
        if(i > len)
                return(0);
        if(i==0)
       {
          eval= max_seq(arr+1, 0, 0, len-1) ;
        }
      else

      {
           eval=0;
      }

  if(arr[i] > last)
	  nFirstIf = arr[i];
  else
	  nFirstIf = last;


  if(arr[i] >= last)
	  nSecondIf = 1;
  else
	  nSecondIf = 0;

  eval2 = max_seq(arr, i+1, nFirstIf, len) + nSecondIf;

      if(eval > eval2)
       {
         return eval ;
        }
      else

      {
           return eval2;
      }

}

**dwks** · 01-16-2009

I don't know why. But here's my annotated solution if you'd like to look at it. My solution prints 7 as expected.

Code:

#include <stdio.h>

#define maximum(a, b) ((a) > (b) ? (a) : (b))

int longest_ascending(int *data, int position, int previous, int length) {
    if(position >= length) return 0;
    
    int longest = 1;
    
    /* This is the first number in a sequence. */
    if(position == previous) {
        longest = maximum(longest,
            1 + longest_ascending(data, position + 1, previous, length));
        
        /* Try starting a sequence at the next position. */
        longest = maximum(longest,
            longest_ascending(data, position + 1, position + 1, length));
    }
    else {  /* This is not the first number in a sequence. */
        /* This number is greater than the previous one;
            try adding it to the sequence.
        */
        if(data[position] > data[previous]) {
            longest = maximum(longest,
                1 + longest_ascending(data, position + 1, position, length));
        }
        
        /* Try leaving this number out of the sequence. */
        longest = maximum(longest,
            longest_ascending(data, position + 1, previous, length));
    }
    
    return longest;
}

int main() {
    int data[] = {-3, -2, -1, 4, 8, 6, 53, 9, 18};
    
    printf("Longest ascending sequence: %d\n",
        longest_ascending(data, 0, 0, sizeof(data) / sizeof(*data)));
    
    return 0;
}

**~~transgalactic2~~** · 01-16-2009

i fixed them thanks

**dwks** · 01-16-2009

Well, you might as well tell us what you did in case other puzzled people are reading this thread and scratching their head.

**~~transgalactic2~~** · 01-16-2009

in the start of this thread i showed the code where it shows the length of the sequence
of cell [0]
so i built an iterative code
and i was thinking how to turn it into a recursive one

**root4** · 01-16-2009

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
}

**~~transgalactic2~~** · 01-16-2009

for this input -9, -8, -7, -6, -5, -99, -3, 9, 18 i get 8
but i should get 5
where is the mistake
??

Code:

#include <stdio.h>

#define maximum(a, b) ((a) > (b) ? (a) : (b))

int longest_ascending(int *data, int position, int previous, int length) {
    
	
    int longest = 1;
	if(position >= length) return 0;
    
    
    /* This is the first number in a sequence. */
    if(position == previous) {
        longest = maximum(longest,
            1 + longest_ascending(data, position + 1, previous, length));
        
        /* Try starting a sequence at the next position. */
        longest = maximum(longest,
            longest_ascending(data, position + 1, position + 1, length));
    }
    else {  /* This is not the first number in a sequence. */
        /* This number is greater than the previous one;
            try adding it to the sequence.
        */
        if(data[position] > data[previous]) {
            longest = maximum(longest,
                1 + longest_ascending(data, position + 1, position, length));
        }
        
        /* Try leaving this number out of the sequence. */
        longest = maximum(longest,
            longest_ascending(data, position + 1, previous, length));
    }
    
    return longest;
}



int main() {
	 
    int data[] = {-9, -8, -7, -6, -5, -99, -3, 9, 18};
    
    printf("Longest ascending sequence: %d\n",longest_ascending(data, 0, 0, sizeof(data) / sizeof(*data)));
    
    return 0;
}

**dwks** · 01-16-2009

for this input -9, -8, -7, -6, -5, -99, -3, 9, 18 i get 8
but i should get 5
where is the mistake
??

I think we're talking about different things. The longest consecutive ascending sequence has length 5: (-9, -8, -7, -6, -5). But the longest ascending subsequence, where you're allowed to jump over numbers, has length 8: (-9, -8, -7, -6, -5, -3, 9, 18).

My program, along with most of the others in this thread, solve the second (and far more complicated problem). I think, from your original description of the problem, that that is what you're actually trying to do.