CODEWITHSUNDEEP
algorithm
JeanClaudeDaudin
JeanClaudeDaudin

Reputation: 435

Number of increasing subsequences in sequence of [0-9] elements

In the case a sequence of unknown range value elements, the question Number of all increasing subsequences in given sequence give us a solution in O(n^2).

I've heard of a solution in O(9*n) in the case of a sequence composed of elements in the interval [0,9] only. If you know this algorithm please let me know about that.

Upvotes: 0

Views: 225

Answers (2)

Romojr50
Romojr50

Reputation: 77

Altering the algorithm linked to in the question, I believe this shall also fulfill the complexity requirement:

input[i] = input array
n = size of input
dp[i] = number of increasing subsequences with i as the last element (same size as input)

initialize dp[i] = 0 for all 0 <= i < n

//Every possible input can be appended on to one previously found
//  increasing subsequence
for (j = 0; j <= 9; j++) {

  //Running total of increasing subsequences that occur earlier in the input using
  //  smaller numbers than j
  int smallerSum = 0;

  for (i = 0; i < n; i++) {

    //This spot in dp was tallied already, need to add it to the running total
    if (input[i] < j) {
      smallerSum += dp[i]

    //Add 1 to the running total, this should be the final answer for this spot in dp
    } else if (input[i] == j) {
      dp[i] = smallerSum + 1;
    }
  }
}

return the sum of all elements of dp

Normally a nested for-loop is a dead giveaway of O(n^2) but in this case we're looping over a constant, making it O(n).

In the general case this algorithm would be O(n*k), where n is the size of the input array and k is the number of possible input values.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18556

Here is an algorithm:

1)Let's call dp[i] = the number of increasing subsequences which have a last element i(0 <= i <= 9). Initially it is filled with zeros.

2)Now we can iterate over the sequence and compute dp in the following way:
Let's assume that the current element is d(0 <= d <= 9). Then dp can be updated like this:

for prev = 0...d - 1
    dp[d] += dp[prev] //continue one of the previous sequences.
dp[d] += 1 //start a new sequence that consists of only one element.

3)After iterating over all the elements of the sequence,
the answer is just the sum of dp[i] for 0 <= i <= 9.

Note that this algorithm has desired complexity only under assumption that arithmetic operations have O(1) time complexity(that might not be the case because the number of increasing subsequences can be very large).

Upvotes: 1

Related Questions