Thread: finding the largest ascending subsequence..

how did you get 5 lines
only the simplest (of checking one cell) case took 14 lines
and its not even comparing between the other results
??

Code:

int max_seq(int *arr, int i, int last, int len)
{
  if (i==len)
   {
    	return 1;
   }
  if (*arr>last)
  {
	  return 1+max_seq(arr,i+1,last,len);
  }
  else
  {
      return max_seq(arr,i+1,last,len);
  }
}

"just 5 lines of code..."
way to go! do you mind posting the code.

its actually very simple.. for every cell you check
a) if theres a bigger sequence starting at the next cell
b) if that sequence is bigger than the sequence starting at this very cell

if we're checking for case a, were not increasing i but arr by one, so the functions can keep track of whether its supposed to calculate a new sequence or add to a existing sequence. (because i will be 0 in case a)

Anyway, heres my function:

Code:

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

i got this example 45 1 21 3 33 6 53 9 18 where the longest is 1 3 6 9 18
it should return 5
and this function returns 4
why??

Code:

#include <stdio.h>
int max_seq(int *arr, int i, int last, int len);
int main()
{
	//45 1 21 3 33 6 53 9 18 
    int array[9] = {45, 1, 21,3,33,6,53,9,18};

    printf("%d\n",max_seq(array,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);
}

duh.. because you can just put 8 numbers into an array of size 9

Code:

#include <stdio.h>

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

int main(void)
{
	int i[] = { 45, 1, 21, 3, 33, 6, 53, 9, 18};
	printf("%d is the longest sequence in i\n", max_seq(i, 0, 0, 9));
	return(0);
}

this works perfectly:

Code:

mk@mk:~$ gcc -o max_seq max_seq.c 
mk@mk:~$ ./max_seq 
5 is the longest sequence in i

thanks

you're welcome

I've had quite some fun thinkin about how to make the solution as short as possible. I'm a minimalist

Originally Posted by transgalactic2

you cant use loops or external functions.

you're using one of those

anyway, I don't think its possible to make the function any shorter than 5 lines without making the code unreadable

do you mean sizeof??

you use two functions in your solution
its not allowed

nah. you have written two functions and the first one calls the second. If I understand that condition correctly, then the task was to have only a single function which calls itself.

edit: damn, transgalactic2 was a couple of seconds faster

Ah! thanks for the clarification; by external functions I thought the op meant the C lib functions.

I copyed and pasted your code and compiled it as it is shown. And it returns 5.

Code:

mk@mk:~$ cat test.c
#include <stdio.h>
int max_seq(int *arr, int i, int last, int len);
int main()
{
         
        int i[] = { 45, 1, 21, 3, 33, 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);
}
mk@mk:~$ gcc -o test test.c
mk@mk:~$ ./test 
5 is the longest sequence in i

my function is perfectly fine