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.

Solution

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;

}

Comments

[MikhaelM]

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