Longest increasing sequence in an array in C

Question

I want to make a program that returns me the longest increasing sequence in an array.

For example:

Input: 1, 2, 3, 2, 6, 2 Output: 1, 2, 3

Input: 4, 3, 1, 2, 4, 6, 4, 1, 5, 3, 7 Output: 1, 2, 4, 6

I managed to put together a code, but this only returns me the first sequence of consecutive, increasing numbers:

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

int main() {
    int j = 0;
    int cou = 0; 
    int max = 0; 
    // c = final array; will contain the longest consecutive, increasing sequence of numbers
    int c[10];
    int n = 0;  
    int a[] = {1, 3, 5, 1, 5, 7, 8, 9, 10, 11, 12};

    for (int i = 0; i < (sizeof(a)/sizeof(int)); ++i) {
        if (a[i+1] > a[i])
            ++cou;
        if (cou > max) {
            max = cou;
            c[j] = a[i];
            c[j+1] = a[i+1];
            j++;
        }
        if (j > n)  //finding the size of my final array
            n = j;
        else {
            cou = 0;
            j = 0;
        }
    }

    for (j = 0; j <= n; ++j) 
        printf("%d ",c[j]);

    return 0;
}

So basically, I want the longest sequence of increasing, consecutive numbers.

Been busting my brains on this one for quite a while now, and still haven't managed to crack it open. Any help is welcome.

If you named your variables something relevant to what they hold (when they're not just simple loop counters), it would be easier to read your code. — mah
– mah, Commented Apr 15, 2014 at 10:47
a[] is my array, c[] should be my final array containing the longest consecutive increasing sequence, cou is a counter that stores the length of the longest sequence of consecutive numbers — MikhaelM
– MikhaelM, Commented Apr 15, 2014 at 10:51
for (int i = 0; i < (sizeof(a)/sizeof(int)); ++i) {: this loop needs to terminate one value sooner, because the next line, if (a[i+1] > a[i]), goes beyond it currently when it references a[i+1]. — mah
– mah, Commented Apr 15, 2014 at 10:55
Also, you only copy elements into c when the current length has already exceeded the prior max length, which means you're skipping elements earlier on. I think it'd be better to not copy anything at all, and instead maintain a longest_start, longest_length, and current_start set of variables. — mah
– mah, Commented Apr 15, 2014 at 11:01

George Birbilis · Accepted Answer · 2020-03-24 23:08:09Z

2

You need to iterate through array, finding sequences, and comparing their length. So, you need to remember previous length of sequence to compare. And you can't copy result to output array on the fly (if you need output array at all), because you can't predict length of next sequence. I'll better show you an example.

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

int main()
{
int previous_len=0, start=0, c[10], len=0;  //c = final array; will contain the longest consecutive, increasing sequence of numbers
int a[] = {1, 3, 5, 1, 5, 7, 8, 9, 10, 11, 12};
for (int i = 0; i < (sizeof(a)/sizeof(int)); ++i) {
    if(a[i+1] > a[i]) {
        len++;
        if (len > previous_len) { 
            previous_len=len;
            start=i+1-len;
        }
    } else {
        previous_len=len;       
        len=0;
    }
}
for(int i = 0; i <= previous_len; ++i) {
    c[i]=a[start+i]; //here you can copy data to output array, if you need it
    printf("%d ",c[i]); //you can output a[start+i] instead
}
return 0;

}

edited Mar 24, 2020 at 23:08

George Birbilis

2,9782 gold badges38 silver badges38 bronze badges

answered Apr 15, 2014 at 11:10

Ryzhehvost

3951 silver badge9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

MikhaelM Over a year ago

Thanks, this worked perfectly and it is a great way of thinking out the problem. I understood (after a while) the code and I have to say that it is very ingenious

user3510955 · Accepted Answer · 2014-04-15 10:45:53Z

0

It seems to mee that you miss some curly braces:

if(a[i+1] > a[i])
{
    ++cou;
    if (cou>max)
        {max = cou;
        c[j]=a[i];
        c[j+1] = a[i+1];
        j++;}
    if (j > n)  //finding the size of my final array
        n=j;
}
else
    {cou = 0;
     j=0;}

answered Apr 15, 2014 at 10:45

user3510955

2 Comments

mah Over a year ago

( and ) are parenthesis. { and } have different names that aren't necessarily agreed upon, but they're definitely not parenthesis. I generally see them referred to as braces, but I'm not certain how standard that is.

user3510955 Over a year ago

Yes, curly braces. Thanks

slim · Accepted Answer · 2014-04-15 10:53:22Z

I suggest breaking this down into smaller pieces.

Start with a function:

int sequenceLength(int[] array, int arrayLen, int position)

... which returns the length of the sequence beginning at position. Test it and make sure it works. You shouldn't need help to write that.

Once you have that, you can write something like:

int longestSequence(int[] array, int arrayLen) {
   int longest = 0;
   int longestLen = 0;
   for(int i=0; i<arrayLen; i++) {
       int seqLen = sequenceLength(array, arrayLen, i);
       if(seqLen > longestLen) {
           longest = i;
           longestLen = seqLen;
       }
   }
   return longest;
}

Again, test this and make sure it works for all circumstances.

Finally you need a function:

printSequence(int[] array, int arrayLen, int position)

... which prints the sequence beginning at that position. Again you should be able to tackle this on your own.

Put all those together:

printSequence(array,arrayLen(longestSequence(array,arrayLen)));

It's always easiest to break a challenge like this into smaller pieces to solve it.

There may be more efficient solutions that avoid backtracking, but guessing at your level, I don't think you need to go there.

(Note: although the code here may compile, consider it as pseudocode)

LearningC · Accepted Answer · 2014-04-15 11:04:05Z

you used a array to store the longest sequence, that made your code go wrong in printing.
And you dint use braces for if() statement that resulted in wrong sequence.
you can make the following changes to make the code work,

int main()
{int j=0, cou=0, max=0, c[10], n=0;  //c = final array; will contain the longest consecutive, increasing sequence of numbers
int a[] = {1, 3, 5, 1, 5, 7, 8, 9, 10, 11, 12};
int i,k,z;
for ( k=0,i = 0; i < (sizeof(a)/sizeof(int)); ++i)
{if(a[i+1] > a[i])
  {  ++cou;
    if (cou>max)
        {max = cou;
        z=k;
        }

   }
    else
        {
            k=i+1;
            cou = 0;
         j=0;}
}
for( j = z; j <(sizeof(a)/sizeof(int)) ; ++j)
if(a[j]<a[j+1])
printf("%d ",a[j]);
else
 break;
printf("%d",a[j]);
return 0;

}

Collectives™ on Stack Overflow

Longest increasing sequence in an array in C

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related