Блог пользователя f.nasim

Longest Increasing Subsequence
Автор f.nasim, 14 лет назад, По-английски
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.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Just google for "longest increasing subsequence" and you'll find it...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Thanks for the suggestion. Can you suggest me some books, links or tutorials which can improve my understanding of dp or greedy algorithms.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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)
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
It can be solved very easy with O(N^2) by DP.
Do you need this solution?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    it can be solved easy with O(NlogN) by DP.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      By sorting all values we had before and binary search on them?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          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?".
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            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.
            → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить