Suppose I have an array 1,2,2,10.
The increasing sub-sequences of length 3 are 1,2,4 and 1,3,4(index based).
So, the answer is 2. Problem LINK
I want a better solution using BIT tree which could improve my solution.
I Have tried using BIT tree but is giving me time limit exceeded error.
Here is BIT implementation Code.
I have also tried direct approach
for (i = 1; i<n;i++)
dp[i, 1] = 1
for (i = 1; i<n;i++)
for (j = 0; j<i-1;j++)
if array[i] > array[j]
for (p = 2; p<k;p++)
dp[i, p] += dp[j, p - 1]
Please help me
Hope this will help..
Every time, you take a value.. calculate how many increasing subsequence you have found and update gradually for length 3,2,1