#include <stdio.h>
 
int MemLIS(int* seq, int* temp, int seq_size)
{
    for (int i = seq_size - 1; i >= 0; i--)
    {
        int max = 0;
        for (int j = i + 1; j < seq_size; j++)
        {
            if (seq[j] > seq[i] && temp[j] > max)
            {
                max = temp[j];
            }
        }
        temp[i] = max + 1;
    }
    int max = 0;
    for (int i = 0; i < seq_size; i++)
    {
        if (temp[i] > max)
        {
            max = temp[i];
        }
    }
    return max;
}
 
int main (void)
{
    int data[] =  {10,1,30,2,19,3,4,5,6,7,8,9,10,11,12,13,14,15,15,16,15,16,16,16,17,17,16,16,16,16,-1};
    int cnt = sizeof(data)/sizeof(data[0]);
    int tmp[cnt];
    printf("Longest %d in %d\n", MemLIS(data, tmp, cnt), cnt);
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgTWVtTElTKGludCogc2VxLCBpbnQqIHRlbXAsIGludCBzZXFfc2l6ZSkKewogICAgZm9yIChpbnQgaSA9IHNlcV9zaXplIC0gMTsgaSA+PSAwOyBpLS0pCiAgICB7CiAgICAgICAgaW50IG1heCA9IDA7CiAgICAgICAgZm9yIChpbnQgaiA9IGkgKyAxOyBqIDwgc2VxX3NpemU7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChzZXFbal0gPiBzZXFbaV0gJiYgdGVtcFtqXSA+IG1heCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbWF4ID0gdGVtcFtqXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICB0ZW1wW2ldID0gbWF4ICsgMTsKICAgIH0KICAgIGludCBtYXggPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzZXFfc2l6ZTsgaSsrKQogICAgewogICAgICAgIGlmICh0ZW1wW2ldID4gbWF4KQogICAgICAgIHsKICAgICAgICAgICAgbWF4ID0gdGVtcFtpXTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gbWF4Owp9CgppbnQgbWFpbiAodm9pZCkKewogICAgaW50IGRhdGFbXSA9ICB7MTAsMSwzMCwyLDE5LDMsNCw1LDYsNyw4LDksMTAsMTEsMTIsMTMsMTQsMTUsMTUsMTYsMTUsMTYsMTYsMTYsMTcsMTcsMTYsMTYsMTYsMTYsLTF9OwogICAgaW50IGNudCA9IHNpemVvZihkYXRhKS9zaXplb2YoZGF0YVswXSk7CiAgICBpbnQgdG1wW2NudF07CiAgICBwcmludGYoIkxvbmdlc3QgJWQgaW4gJWRcbiIsIE1lbUxJUyhkYXRhLCB0bXAsIGNudCksIGNudCk7CiAgICByZXR1cm4gMDsKfQo=