Fetus86_and_Luki49's blog

Help Needed In Dp Problem
By Fetus86_and_Luki49, history, 4 years ago, In English

How to implement Longest non-decreasing subsequence using recursion+memoization method efficiently? Will be grateful if anyone can help. Thank You.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a better approach Link

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Define function F(id) — "longest non-decreasing subsequence that ends at position id".

Recurrence formula : $$$ F(id) = max(F(id) , F(k) + 1) , 0 <= k < id,value[id] >= value[k]$$$

$$$Answer = max(F(i)), 0 <= i < n$$$ — where n is the number of elements.

IDEA: Find the longest non-decreasing subsequence ending at each position. Now the longest subsequence ends at some position i, so all we need is to find the position such that length of non-decreasing subsequence ending at that position is maximum.

CODE

→ Reply