Longest Monotone Subsequence

Posted on Edited on In
最长单调子序列的动态规划/贪心+二分查找算法

严格单调递增子序列

求a[n]的最长严格单调递增子序列长度，简称LMS

思路1：动态规划

考虑dp[i]=以a[i]结尾的最长LMS

  • 首先，对于a[1]，最长严单增子序显然是它本身，也就是长度为dp[1]=1
  • 对于i>1，考虑a[i]与a[j], 1 <= j < i
    • 如果a[j] < a[i]，那么显然a[j]结尾的最长严单增子序，尾部再加上一个a[i]，仍然严单增
    • 如果a[j] >= a[i]，那么反之，a[i]不能与a[j]结尾的子序列构成最长严单增子序
  • 则有dp方程：dp[i] = Max{dp[i], dp[j] + 1 if a[j] < a[i] else 1}

时间复杂度：O(n^2)

空间复杂度：O(n)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// cmp： < 时为最长严单增子序列； <= 时为最长单增子序列； 反之为相应的递减
template <class Compare>
int32_t LongestMonotoneSubsequence(const int32_t *a, const size_t &n,
                                   const Compare &cmp) {
  if (n == 0 || a == nullptr) return 0;

  int32_t res = 1, *dp = new int32_t[n];

  for (int i = 0; i < n; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j)
      if (cmp(a[j], a[i]) && dp[i] <= dp[j]) dp[i] = dp[j] + 1;
    if (res < dp[i]) res = dp[i];
  }

  delete[] dp;
  return res;
}

思路2：贪心+二分查找

  • 考虑计算dp[i]时：
  • 有x, y < i，且a[x] < a[y] < a[i]，且dp[x] = dp[y]，那么选择x显然比选择y更好
  • 所以可以使用贪心：维护一个数组b[]，使得b[j], 1<=j<=t为a[i], 1<=i<=n中长度为j的最长单调子序列中尾元素的最小值
  • 那么，当a[i] > b[t]时，显然dp[i] = b[t]+1，同时要令b[++t] = a[i]
  • 反之，从b[j], 1<=j<=t中找出第一个满足b[j]>=a[i]的，令b[j] = a[i]
  • 可以发现最终dp[n] = t，故可省去dp[i]
  • 可以发现b[]是满足严单增的，故a[i] <= b[t]时可用二分法查找

时间复杂度：O(nlogn)

空间复杂度：O(n)

模板

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
// cmp： < 时为第一个大于key的； <= 时为最后一个等于或第一个大于； 反之为相应的
template <class Compare>
int32_t BinarySearch(const int32_t *a, const size_t &n, const int32_t &key,
              const Compare &cmp) {
  size_t lp = 0, rp = n - 1, mp;
  if (cmp(a[rp], key)) return n;

  while (lp != rp) {
    mp = (lp + rp) >> 1;
    if (cmp(a[mp], key)) {
      lp = mp + 1;
    } else {
      rp = mp;
    }
  }
  return lp;
}

// cmp： < 时为最长严单增子序列； <= 时为最长单增子序列； 反之为相应的递减
template <class Compare>
int32_t LongestMonotoneSubsequence(const int32_t *a, const size_t &n,
                                   const Compare &cmp) {
  if (n == 0) return 0;

  int32_t res = 0, *b = new int32_t[n];
  b[0] = a[0];

  for (int i = 1; i < n; ++i) {
    if (cmp(b[res], a[i])) {
      b[++res] = a[i];
    } else {
      b[BinarySearch(b, res, a[i], cmp)] = a[i];
    }
  }

  delete[] b;
  return res + 1;
}