Блог пользователя HitmanBBa

LIS [Help].
Автор HitmanBBa, история, 9 лет назад, По-английски

Greetings.

There is any O(N LOG K) algorithm for longest not strictly increasing subsequence?

Example for longest not strictly increasing subsequence:

n = 3
a[] = {1, 1, 1}

Normal O(N LOG K) algorithm will give answer = 1. (Because it's work strictly increasing)

I need modified algorithm to give answer = 3.

Thanks in advance.

Теги lis, dp
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится 
vector<int> input, lis;
int n;//sizeof input
for (int i = 0; i < n; i++){
    int pos = upper_bound(lis.begin(), lis.end(), input[i]) - lis.begin();
    if (pos == lis.size())
         lis.push_back(input[i]);
    else
         lis[pos] = input[i];
}
//lis.size() is the answer
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh man, you saved my life.

    Thank you very much, you are my hero :D.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      you're welcome :) if you replace upper_bound with lower_bound, it gives you the normal lis.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        One last question.

        How to build the solution?

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится

          for each i, I define l[i] = longest nondecreasing subsequence which ends on the ith position of input prv[i] = the index which we update l[i] from.

          I modify vector<a[j]> lis to vector<pair<a[j], j>> lis. now you can see that on the ith iteration of the algorithm, we get l[i] = pos, prv[i] = lis[pos — 1].second.

          now run a recursive algorithm starting from such index z that l[z] = lis.size() and use prv to build the solution.

          → Ответить