# Counting the number of increasing sub-sequences

The problem is to find the number of increasing sub-sequence of a string with only digit characters. Answer may be very large, so output it modulo 10^9+7.

I have been able to get a O(n) solution using segment trees. However , the the code is quite inefficient owing to loops with constant but large runtime. How can I make the code more efficient ?

The link to the exact problem statement is http://www.spoj.com/problems/LARSUBP/

#include <stdio.h>
#include <string.h>

typedef struct Tree_node
{
int M[10][10] ;
// M[i][j] = Number of sub-sequences starting with i and ending with j in the interval low to high in which it is called .
} TN ;

//Declaration of global variables

char number[50000] ;//Stores the input string
TN Tree[100000] ;//The array Tree[] is used to store the nodes of the segment tree
long long int convert ; //Other variables
int k1 , k2, i , j;

void Build_Tree( int node , int low , int high) ;

int main()
{
// t is the number of test cases
// N is the length of input string
int t , N , counter ;

//Stores the number of increasing sub-sequences

//No of test cases
scanf("%d",&t) ;

for(counter=0;counter<t;counter++)
{
scanf("%s",number) ;
N = strlen(number) ;

// Calling the build tree function
Build_Tree(1,0,N-1) ;

// Calculation of increasing sub-sequences using the Tree .
for(i=0;i<10;i++)
{
for(j=i;j<10;j++)
{
}
}

}
return 0 ;
}

void Build_Tree( int node , int low , int high)
{

// node stores the index of the Tree-node to be evaluated
// low and high define the interval which we are considering

int mid ;

// Initialization of M[][]
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
Tree[node].M[i][j] =0 ;

}
}

if(low==high)
{
// Base case
int temp = number[low]- '0' ;
Tree[node].M[temp][temp] = 1 ;
}
else
{
mid = (low+high)/2 ;
Build_Tree(2*node , low , mid) ; // Building the subtree of left child
Build_Tree(2*node+1 , mid+1 , high) ; // Building the subtree of right child

// Combining the information
// No. of increasing sub-sequences starting with i and ending withj from low to highequal to sum of
// 1.increasing sub sequences starting with i and ending with j from low to mid
// 2.increasing sub sequences starting with i and ending with j mid+1 to high
//3. all increasing sub-sequences starting with i and ending with k1 from low to mid multiplied by increasing sub sequences starting with k2 and ending with j from mid+1 to high where k1 < k2 .

for(i=0;i<10;i++)
{
for(j=i;j<10;j++)
{
convert = Tree[2*node].M[i][j] + Tree[2*node+1].M[i][j] ;
convert = convert % 1000000007 ;
Tree[node].M[i][j] = convert ;

if(i==j)
{
continue ;
}
else
{

for(k1=i;k1<j;k1++)
{
for(k2=k1+1;k2<=j;k2++)
{
convert = Tree[node].M[i][j] + Tree[2*node].M[i][k1] * Tree[2*node+1].M[k2][j] ;
convert = convert % 1000000007 ;
Tree[node].M[i][j] = convert ;

}
}
}

}
}

}

}


$\newcommand{\sub}[1]{\text{sub}_{#1}}$ This is more of an alternative algorithm than a review on your code (at least for now), but it seems like both could be helpful.

A good algorithm results from solving a slightly more informative version of the problem, which is simpler to decompose:

$\sub{s}^n$ is the number of subsequences of $s$ that are ordered and end with the digit $n$.

$\sub{s}$ can be stored in a 10-long array, the sum of which solves your original problem:

$$\left[\ \sub{s}^0;\ \text{sub}_s^1;\ \text{sub}_s^2;\ \ldots;\ \text{sub}_s^9\ \right]$$

Clearly, for the empty string $\varnothing$, we have

$$\text{sub}_\varnothing = \left[\ 0;\ 0;\ 0;\ \ldots;\ 0\ \right]$$

The interesting trick is that extending a string $s$ with digit $d$ is a simple update

$$\sub{sd}^n = \begin{cases} \sub{s}^n & \text{if}\;n \ne d\\ 1 + \sum_{i=0}^{n} \sub{s}^i & \text{if}\;n = d \end{cases}$$

as the paths for subsequences that don't end in $d$ are unchanged and the subsequences that do end in $d$ are $d$ itself, $d$ added to the end of any prior subsequence that ends in a digit less than $d$, or any of the prior subsequences that did end with the digit already.