随笔 - 最长下降子序列问题的 O (n log n) 解法

发表于 更新于 分类于 本文字数： 270 阅读时长 ≈ 1 分钟

科普文，看看就好

算法流程

设 a[] 为原序列，s[] 为辅助数组

  1. a 中第一个元素插入 s 的末尾

  2. 遍历 a, 从第二个元素取到最后一个

    1. 如果当前遍历到的元素小于 s 的末尾，则将其插入 s 的末尾

    2. 否则在队内二分查找比当前元素大的最小元素，将该元素替换为当前遍历到的元素

      如果找不到这样的元素，则清空 s 并将当前遍历到的元素插入 s 的末尾即可

      因为此时除了 s 末尾的元素之外，s 内的其余元素不会影响到答案

      而当前遍历到的元素更有可能成为最长下降子序列内的元素

      故直接替换即可

  3. s 的长度即为最长下降子序列长度

复杂度

令原序列长度为 \(n\)

  • 时间复杂度: \(O(n\log n)\)
  • 空间复杂度: \(O(n)\)

代码

Show code

main.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

deque<int> a;
vector<int> s;

int main() {
  int _;
  while (cin >> _) a.push_back(_);
  if (a.empty()) {
    cout << 0 << endl;
    return 0;
  }
  s.push_back(a.front());
  a.pop_front();
  for (int num : a) {
    if (num < s.back()) s.push_back(num);
    else *lower_bound(s.begin(), s.end(), num, greater<int>()) = num;
    // print s
    // for (int num : s) clog << num << " ";
    // clog << endl;
  }

  cout << s.size() << endl;
  return 0;
}

/* input:
89 126 85 103 101 86 86 98 96 99 89 81 101 92 79 77 82 97 83 100 78 72 79 97 71
80 98 89 69 74
*/

/* expected output:
12
*/