Longest Increasing Subsequences

Question

For a digit N we define LIS Array as

Longest strictly increasing subsequence of digits ending with that digit.

For example, let us say 4-digit number is 1531, then the LIS array would be [1, 2, 2, 1].

The length of longest increasing subsequence ending at first digit is 1 (the digit 1 itself) and at the second digit is 2 ([1, 5]), at third digit is also 2 ([1, 3]), and at the 4th digit is 1 (the digit 1 itself).

Problem Statement

Here i am using bitmasking algorithm

for(int i=2;i<=n;i++){
    int x = Lis[i];

    if(x==1){
        for(int j=1;j<(1<<10);j++){
            int last=-1;
            int len=0;
            for(int k=9;k>=0;k--)
                if((j&(1<<k))!=0){ 
                    len++;
                    if(len==1)
                        last=k;
                }

            for(int k=0;k<=last;k++){
                dp[1<<k][i] = (dp[1<<k][i]+ dp[j][i-1])%mod;
            }
        }

        continue;
    }

    for(int j=1;j<(1<<10);j++){
        int last=-1;
        int len=0;
        for(int k=9;k>=0;k--)
            if((j&(1<<k))!=0){ 
                len++;
                if(len==1)
                    last=k;
            }
        if(len+1!=x) continue;

        for(int k=last+1;k<10;k++)
            dp[j|(1<<k)][i] = (dp[j|(1<<k)][i]+ dp[j][i-1])%mod; 
    }
}

But it's not working correctly ? Can anyone explain me correct approach to deal with this ?

well, technically speaking this isn't a subsequence, as sequences are defined as consecutive integers. And debugging some deeply nested code with ambiguous variable-names and no documentation is definitely nothing anyone will do for you. Please either refactor your code, or add a bit of explanation. — Paul

Paul Paul · Accepted Answer · 2017-01-24T11:08:58

For each digit store the length of the longest associated sequence and go through the sequence:

max_len[]
result

for digit in sequence
    max_len[digit] = max(sub_array(max_len, 1, digit - 1)) + 1
    result.append(max_len[digit])

since max_len has length 9 or 10, depending upon whether 0 is allowed in the input-sequence, this solution runs in O(n). result contains the LIS-array.

The basic idea is to define the LIS of an element e in the input-sequence recursively as the LIS of any element that precedes e and is smaller than e. Since we want the longest sequence we obviously choose the predecessor with the longest sequence. We can memorize this value as the longest sequence that ends with element e for later use and add the length of the LIS of e to the output sequence.

Longest Increasing Subsequences

1 Answers