Counting Increasing Subsequences of size K recursive

The original description of the problem can be found here, its input here and its expected output here.

The problem:


Given a integer sequence a1 ... an (-10000
\$\leq\$ ai \$\leq\$ 10000). Where n (1 \$\leq\$ n
\$\leq\$ 100),the size of the sequence, is a given number.


Find the number of increasing subsequences with length equals to a
given size k (1 \$\leq\$ k \$\leq\$ n \$\leq\$ 100).


An increasing subsequence ai1 ... aix of a
sequence a1 ... an is defined as

aix-1, \$ix for all 1 \$<\$ x \$\leq\$ n).


The input has several testcases. The first line contains the numbers
n and k. The second line contains a sequence of length n. 0 0 ends the input. The sequence will be given in a way that the
subsequences count can't be bigger than a signed number of 64 bits.


Example:

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

The output is the number of increasing subsequences:


Example for the above input:

252
0

My solution uses a recursive idea. The sequence values are stored in an array of size n+1 with a \$-\infty\$ in the 0 index of the array. After this, a function goes from de 0 index to de n position recursively. And a comparison is made to check if the current value (picked) is less than the next value.

```
#include
#include
#include

long long memoization[102][102];

long long LCIS(int *S,int len,int picked,int LCISlen, int K){
if(memoization[picked][LCISlen])
return memoization[picked][LCISlen];

long long q = 0;

int i;
for (i = picked + 1; i < len; i++) {
if(S[picked] < S[i] && LCISlen < K)
q += LCIS(S, len, i, LCISlen + 1, K);
else if(S[picked] < S[i] && LCISlen == K)
q++;
}

return memoization[picked][LCISlen] = q;
}

int main(){

int N,K;
while(scanf("%d %d",&N,&K), (N != 0) && (K != 0)){

int i, S[N+1];

S[0] = INT_MIN;

for (i = 1; i <= N; i++)
scanf("%d",&S[i]);

m

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 >= 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  seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k >= 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 
#include 
#include 

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 >= 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  seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k >= 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",&n,&k), n != 0 && k != 0) {

        int sequence[n];

        for (int i = 0; i < n; i++) {
            scanf("%d", &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.

StackExchange Code Review Q#93227, answer score: 11