I am finding it hard that how to find the number of increasing sequences of length k in n numbers. I know it has use of LIS problem and i have to modify it somehow, but now getting how. it’s complexity is O(k*n^2) DP solution. Please give hint and explain me a little bit.
My hint is:
number of inc. seq. of length k in n elements = ( number of inc. seq. of length k - 1 in n - 1 elements ) + ( number of inc. seq. of length k in n - 1 elements )
You simply use or skip first element. Additionally you need to remember last chosen number (you need to select bigger next time) and it makes O(k*n*n) when you normalize elements in sequence to range [0,n).
1 Like
It is very effective codechef with the information of world wide. It is well written and effective also it is very informative about on There are Oil paintings for sale on the market all right where you are and all all over the globe. If you cannot discover a supplier that you like or believe in, make time to look on the internet for one and you may be amazed. Usually on the internet traders and performers are able to provide you costs that are less and excellent that is fantastic.
You can look through this link and link . Basically the link provides you with pseudo code for @betlista’s idea.
number of inc. seq. of length k in n elements = ( number of inc. seq. of length k - 1 in n - 1 elements ) + ( number of inc. seq. of length k in n - 1 elements )
Can u write that DP[i] ? that when i have calculated the LIS array, then next what i need to change in that ?