Finding total number of subsequences in an array with consecutive difference = k

Question

In the given array, I am trying to find the total number of subsequences such that:

• the difference between the consecutive terms is not greater than 3
• the first element of the subsequence is the first element of the array
• the last element of the subsequence is the last element of the array

For example, in an array: [10,13,7,8,14,200, 876, 11], it has 5 subsequences which follow the above condition.

I am trying a bottom-up approach to this. I tried the following, but it does not give all the subsequences and outputs 4 instead of 5.

How can I approach this? I have an intuition that the approach could be similar to Longest Increasing Subsequence, but not sure how.

Answer 1

Let f(i) be the number of subsequences that fulfill the following conditions:

• Start by A[0]
• End by A[i]
• The difference between the consecutive terms is not greater than 3
  

Then the answer to your problem will be f(A.length()-1).

Here is the code in C++ in a bottom-up approach:

int A[] = {10,13,7,8,14,11};
int f[6];
int n = 6;
    
for (int i=0;i<n;i++) f[i] = 0;
f[0]=1;
for (int i=1;i<n;i++){
  for (int j=0;j<i;j++){
     if (abss(A[i] - A[j]) <= 3)
         f[i] += f[j];
  }
}
cout<<f[n-1]<<endl;//printing the result

Here is the code written in C++ in top-down approach:

int A[] = {10,13,7,8,14,11};
int n = 6;

int memo[6];//initialized with -1s;

int count(int currIndex){
  if (currIndex == n-1) return 1;
  if (memo[currIndex] != -1) return memo[currIndex];
  
  int res = 0;
  for (int i=currIndex+1 ; i<n ; i++){
      if (abss(A[currIndex] - A[i]) <= 3){
            res += count(i);
      }
  }
    
  memo[currIndex] = res;
  return res;
}

And the result will be by calling count at first index like this:

count(0);