Number of all increasing subsequences in given sequence?

Question

You may have heard about the well-known problem of finding the longest increasing subsequence. The optimal algorithm has O(n*log(n))complexity.

I was thinking about problem of finding all increasing subsequences in given sequence. I have found solution for a problem where we need to find a number of increasing subsequences of length k, which has O(n*k*log(n)) complexity (where n is a length of a sequence).

Of course, this algorithm can be used for my problem, but then solution has O(n*k*log(n)*n) = O(n^2*k*log(n)) complexity, I suppose. I think, that there must be a better (I mean - faster) solution, but I don't know such yet.

If you know how to solve the problem of finding all increasing subsequences in given sequence in optimal time/complexity (in this case, optimal = better than O(n^2*k*log(n))), please let me know about that.

In the end: this problem is not a homework. There was mentioned on my lecture a problem of the longest increasing subsequence and I have started thinking about general idea of all increasing subsequences in given sequence.

Answer 1

I don't know if this is optimal - probably not, but here's a DP solution in O(n^2).

Let dp[i] = number of increasing subsequences with i as the last element

for i = 1 to n do
    dp[i] = 1
    for j = 1 to i - 1 do
        if input[j] < input[i] then
            dp[i] = dp[i] + dp[j] // we can just append input[i] to every subsequence ending with j

Then it's just a matter of summing all the entries in dp

Answer 2

You can compute the number of increasing subsequences in O(n log n) time as follows.

Recall the algorithm for the length of the longest increasing subsequence:

For each element, compute the predecessor element among previous elements, and add one to that length.

This algorithm runs naively in O(n^2) time, and runs in O(n log n) (or even better, in the case of integers), if you compute the predecessor using a data structure like a balanced binary search tree (BST) (or something more advanced like a van Emde Boas tree for integers).

To amend this algorithm for computing the number of sequences, store in the BST in each node the number of sequences ending at that element. When processing the next element in the list, you simply search for the predecessor, count the number of sequences ending at an element that is less than the element currently being processed (in O(log n) time), and store the result in the BST along with the current element. Finally, you sum the results for every element in the tree to get the result.

As a caveat, note that the number of increasing sequences could be very large, so that the arithmetic no longer takes O(1) time per operation. This needs to be taken into consideration.

Psuedocode:

ret = 0
T = empty_augmented_bst() // with an integer field in addition to the key
for x int X:

  // sum of auxiliary fields of keys less than x
  // computed in O(log n) time using augmented BSTs
  count = 1 + T.sum_less(x)

  T.insert(x, 1 + count) // sets x's auxiliary field to 1 + count
  ret += count // keep track of return value

return ret