Number of Increasing Subsequences of length k

Question

I am trying to understand the algorithm that gives me the number of increasing subsequences of length K in an array in time O(nklog(n)). I know how to solve this very same problem using the O(k*n^2) algorithm. I have looked up and found out this solution uses BIT (Fenwick Tree) and DP. I have also found some code, but I have not been able to understand it.

Here are some links I've visited that have been helpful.

Here in SO
Topcoder forum
Random webpage

I would really appreciate if some can help me out understand this algorithm.

mind showing the code you found that has O(n*k*log(n)) complexity? — taocp, May 06 '13 at 16:20
It is easier to think about this without trying to do it with BIT straight away. I explain how here: http://stackoverflow.com/questions/15057591/how-to-find-the-total-number-of-increasing-sub-sequences-of-certain-length-with/15058391#15058391 — IVlad, May 06 '13 at 17:02
I cannot understand your algorithm. Could you please expand your explanation here in my post, and maybe give me an idea of that using Segment Trees, I will then come up with a solution using BIT. Thanks in advance — Andrés, May 06 '13 at 21:45
I have added some more explanations. Let me know exactly what isn't clear if you still have trouble understanding it and I will do my best to help. — IVlad, May 06 '13 at 22:38

score 7 · Accepted Answer · edited May 23 '17 at 10:29

I am reproducing my algorithm from here, where its logic is explained:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
         have a certain length

for i = 1 to n do   dp[i, 1] = 1

for p = 2 to k do // for each length this time   num = {0}

  for i = 2 to n do
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element
    // have length p - 1
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1*   

    // append the current element to all those smaller than it
    // that end an increasing subsequence of length p - 1,
    // creating an increasing subsequence of length p
    for j = 1 to array[i] - 1 do *2*       
      dp[i, p] += num[j]

You can optimize *1* and *2* by using segment trees or binary indexed trees. These will be used to efficiently process the following operations on the num array:

Given (x, v) add v to num[x] (relevant for *1*);
Given x, find the sum num[1] + num[2] + ... + num[x] (relevant for *2*).

These are trivial problems for both data structures.

Note: This will have complexity O(n*k*log S), where S is the upper bound on the values in your array. This may or may not be good enough. To make it O(n*k*log n), you need to normalize the values of your array prior to running the above algorithm. Normalization means converting all of your array values into values lower than or equal to n. So this:

5235 223 1000 40 40

Becomes:

4 2 3 1 1

This can be accomplished with a sort (keep the original indexes).

There is something I have not been able to understand. How does this algorithm guarantees that you are storing the number of INCREASING Subsquences. I know how the DP O(n*n*k) does, but this one... Not a clue — Andrés, May 07 '13 at 01:42
@Andrés - basically, you count how many of a certain length you have for each **value** (not index like in the classic DP). You can append the current value to all smaller values, obtaining +1 length. — IVlad, May 07 '13 at 08:49

Number of Increasing Subsequences of length k

1 Answers1

Linked

Related