Using dynamic programming to find the number ofl increasing subsequences [closed]

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing sub-sequences for every index j, that end with Xj.

My solution should include a recurrence formula that solves this problem in O(n^2) and a correctness proof, I was only able to solve it using a nested for loop and I'm not sure if there's an O(n^2) recursion solution.

List a[1…n] <- [1…1]
For j= 1 to n
For i= 1 to j-1
If xi<xj then
a[i]= a[j]+a[i];

closed as unclear what you're asking by D.W.♦, David Richerby, André Souza Lemos, Luke Mathieson, JuhoJul 6 '15 at 6:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to Computer Science Stack Exchange. This site is intended as cooperative. Since you seem to have worked on i, could you tell us what you tried, what you do not understand, what is blocking you. It is important for you to try on your own, and for us to answer the specific issues that may be a problem. Don't you feel that the second sentence is a bit too imperative for a request? – babou Jul 2 '15 at 21:45
• your absolutely right! edited my post and added my solution. – TCP_Explorer Jul 3 '15 at 6:15
• So your question is only whether it is $O(n^2)$. Well, this double loop is a pretty standard case for it, and you should find lots of examples.with precislely the same kind:: for J=1 to n for i= 1 to j-1 making a total of $(n-1)n/2$ steps (the sum of the first $n-1$ integers). Check your notes or examples. --- Regarding your solution, do you have at least an explanation for it hat could be the start of a proof? – babou Jul 3 '15 at 6:49
• No, I'm not asking whether it is O(n^2), I'm trying to solve this problem using a dynamic programming style (recursion/memoization). – TCP_Explorer Jul 3 '15 at 8:36
• Well, we try our best to understand what your specific problem is. But you have to state clearly what the question is, and have that in the question, not i a comment. So I guess you want a recursive version of what you wrote. --- BW I think you mixed up i and j in the last line of code. – babou Jul 3 '15 at 9:08

The recursive equivalent of what you wrote is:

function S(j) is
r <- 1
For i <- 1 to j-1
if xi<xj then
r <- r+S(i)
return r

It is very similar to what you wrote, except that a is replaced by S(i), i.e., a recursive call to the function, since it is the function that is supposed to compute the number of sequences that you store in a[i]. The array a is used to remember previous results, and the new result you are computing is obtained using the previous results.

This array is no longer needed, as it is replaced by the memoization of the dynamic programming interpretation of the recursive function. If I understood correctly what you are asking.

Now, to do the proof, you should explain why computing in this way is correct.

This works with the same costs as your algorithm, provided the recursion is interpreted with dynamic programming memomization, and you should be able to prove it easily.

Of course standard recursive execution of the function, without memoization of results, is a lot more costly.

• Thanks @babou, I'm trying to think on how the recurrence formula looks for this as there is no stop condition in the recursion. – TCP_Explorer Jul 3 '15 at 10:47
• @TCP_Explorer Actually, there is a stop condition, but it is not very visible. You want the recursion to stop when j==1. So you should check what actually happens when j==1, you will see there is no recursive call. But you are right: it is always wise to check for the stopping condition, as well as for something that decreases to some lower bound at each recursive call. – babou Jul 3 '15 at 11:07
• @TCP_Explorer Did you find how it stops? --- BTW you know you can upvote and possibly accept answers when they are interesting or useful to you (see cs.stackexchange.com/tour), or downvote when an answer is wrong. It is the local way of showing appreciation for the work of others. – babou Jul 4 '15 at 8:13
• Thanks! I did understand how it works, except it doesn't use memoization and I'm not sure about the recurrence formula. Thanks! – TCP_Explorer Jul 5 '15 at 12:19
• Notice you do not use another array to store the values you recursively get, so that part is missing for the "dynamic planning" part – TCP_Explorer Jul 5 '15 at 12:27