f.nasim's blog

Longest Increasing Subsequence
By f.nasim, 14 years ago, In English
Given an unsorted sequence A={a0,a1,a2,......an-1} of n integers. How do I find the longest increasing sub-sequence of the given sequence. Is there any dynamic programming solution.
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Just google for "longest increasing subsequence" and you'll find it...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks for the suggestion. Can you suggest me some books, links or tutorials which can improve my understanding of dp or greedy algorithms.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The classical "Introduction to algorithms" has a very good chapter on these subjects; the number of examples is quite small, but they are discussed thoroughly. Other than that, I don't know... I can only suggest the tutorial at Topcoder (I haven't read it, but at least it contains a list of problems)
      → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
It can be solved very easy with O(N^2) by DP.
Do you need this solution?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    it can be solved easy with O(NlogN) by DP.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      By sorting all values we had before and binary search on them?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No.
        A[i] - our sequence
        DP[i] = the length of the LIS ending with element numbered i.
        We'll keep track of vector V as follows:
        V[j] = A[k], such that dp[k] = j and k is the largest number < i, satisfying this condition.
        Suppose, we have found out all the dp[1..i-1], and V is up to date. How to find dp[i]? It's easy to find by binary search on V, isn't it? OK, find it, and don't forget to update V.
        Start with dp[1] = 1 and V[1] = A[1] (1-based sequence)
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Condition "V[j] = A[k], such that dp[k] = j and k is the largest number < i, satisfying this condition" guaranties us than elements in V is already sorted.
          I mean that when saying "By sorting all values we had before and binary search on them?".
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Yes, V remains sorted. But we do NOT sort V. All we do to V is
            1) override elements in V and
            2) append elements to V.
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Yeah. I understood at once that we don't need to sort V . ^_^
              → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
BTW, my favourite problem on LIS is problem J from NEERC 2004 "Joke with turtles".
You can try to solve it here: http://acm.tju.edu.cn/toj/showp2400.html
→ Reply