Counting Increasing Subsequences of size K recursive
Concept

You have called this a "Longest Increasing Subsequence" problem, but it's not, is it? It's counting all possible sequences of a specific length, not just the longest. As a result, I think you may have confused yourself in a few ways....

Naming

Your variable and method names are ... horrible. Variables should always be useful names, and, while N and K are referenced in the problem specification, S is not. Additionally, upper-case names are not encouraged... so you should have n and k instead. The method name LCIS is also off, it should be longest_increasing_sequence, and where does the C in LCIS come from?

Standards

Your code compiles OK (with a warning about the missing return in the main method) with basic C compiler. This makes me think you intend to use C99 which compiles it without warnings. But, in C99, you should declare your variables where they are used, not at the beginning of the blocks. For example, you should declare i inside the for-loop.

Globals

Globals are to be avoided.

Algorithm

Your concept of memoization is good, but I am not convinced the recursion is doing what you think it does. I am not convinced the memoization is used at all effectively. Frankly, I struggled to follow your algorithm, in part because memoization does not tell me much about what is being memoized...

I started hacking your code, and ended up restructuring it as a set of nested loops. The resulting complexity is somewhere around \$O(n^3)\$, which sounds really bad, but, for the problem given I am not sure can be improved on... A large part of the complexity is in the determination of the paths, not the combinatorics required to compute the count. I am likely wrong here somewhere, but my performance of the resulting code is more than good enough to be in the right ballpark...

So, I use memoization as well, the system I use is, for each node, starting from the last, to record the number of increasing paths, and how long they are, to the end of the sequence. The last node, for example, can be the last node in the sequence, and thus has a count of 1 in path-length 0 (0 because I zero-base the path length - 0 really means "there is 1 path starting from this node where this node is the last member too").

With that system, I can then work backwards through the sequence, and simply add up the paths that have the right length.

The critical method looks like:

long long count_sequences(const int *seq, const int size, const int path) {
    long long pathcounts[size][size];

    memset(pathcounts, 0, sizeof(pathcounts[0][0]) * size * size);

    long long count = 0;

    // start from end and work back.
    for (int i = size - 1; i &gt;= 0; i--) {
        //printf("  start %d at %d\n", seq[i], i);
        // always 1 step from here to end.
        pathcounts[i][0] = 1;
        for (int j = i + 1; j &lt; size; j++) {

            // check for increasing sequence
            if (seq[j] &gt; seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k &gt;= 0; k--) {
                    pathcounts[i][k + 1] += pathcounts[j][k];
                }
            }
        }
        // zero-based path length - must subtract 1
        count += pathcounts[i][path - 1];
    }

    return count;
}


Note how, at each level we have to look ahead for increasing members, but, we only need to look in to the memoization for increasing members to accumulate path lengths.

Note also how we can accumulate the count as we retreat?

The entire program I have is:

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;limits.h&gt;

long long count_sequences(const int *seq, const int size, const int path) {
    long long pathcounts[size][size];

    memset(pathcounts, 0, sizeof(pathcounts[0][0]) * size * size);

    long long count = 0;

    // start from end and work back.
    for (int i = size - 1; i &gt;= 0; i--) {
        //printf("  start %d at %d\n", seq[i], i);
        // always 1 step from here to end.
        pathcounts[i][0] = 1;
        for (int j = i + 1; j &lt; size; j++) {

            // check for increasing sequence
            if (seq[j] &gt; seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k &gt;= 0; k--) {
                    pathcounts[i][k + 1] += pathcounts[j][k];
                }
            }
        }
        // zero-based path length - must subtract 1
        count += pathcounts[i][path - 1];
    }

    return count;
}

int main(){

    int n,k;
    while(scanf("%d %d",&amp;n,&amp;k), n != 0 &amp;&amp; k != 0) {

        int sequence[n];

        for (int i = 0; i &lt; n; i++) {
            scanf("%d", &amp;sequence[i]);
        }

        long long count = count_sequences(sequence, n, k);

        printf("%lld\n", count);
    }
}


On my computer, with -Wall and -O3, it runs the full dataset in 0.01 seconds.