algorithm - 具有特定属性的最长公共(public)子序列？

Question

我们说数字序列 x(1),x(2),...,x(k) 是之字形 如果它的三个连续元素都没有创建非递增 或非递减 序列。更准确地说，对于所有 i=1,2,...,k-2 要么

x(i) >( x(i+1),x(i-1) )  

or

x(i) < ( x(i+1) , x(i-1))

我有两个数字序列 a(1),a(2),...,a(n) 和 b(1),b(2),.. .,b(m)。问题是计算最长公共(public)之字形子序列的长度。换句话说，您要从两个序列中删除元素，使它们相等，并且它们是一个之字形序列。如果执行此操作所需的最少元素数是 k，那么你的答案是 m+n-2k。

注意。长度为 2 和 1 的序列通常是锯齿形的

现在我尝试使用下面的状态变量编写一个内存递归解决方案

i= current position of sequence 1.
j= current position of sequence 2.
last= last taken number in the zigzag sequence currently being considered.
direction = current requirement of the number i.e. should it be greater than previous,less or same;  

我调用下面的函数

magic(0,0,Integer.MIN_VALUE,0);

这里使用了 Integer.MIN_VALUE 标记值，表示序列中还没有数字。函数如下:

static int magic(int i, int j, int last, int direction) {

  if (hm.containsKey(i + " " + j + " " + last + " " + direction))
   return hm.get(i + " " + j + " " + last + " " + direction);


  if (i == seq1.length || j == seq2.length) {
   return 0;

  }



  int take_both = 0, leave_both = 0, leave1 = 0, leave2 = 0;
  if (seq1[i] == seq2[j] && last == Integer.MIN_VALUE)
   take_both = 1 + magic(i + 1, j + 1, seq1[i], direction); // this is the first digit  hence direction is 0.
  else if (seq1[i] == seq2[j] && (direction == 0 || direction == 1 && seq1[i] > last || direction == -1 && seq1[i] < last))
   take_both = 1 + magic(i + 1, j + 1, seq1[i], last != seq1[i] ? (last > seq1[i] ? 1 : -1) : 2);


  leave_both = magic(i + 1, j + 1, last, direction);

  leave1 = magic(i + 1, j, last, direction);
  leave2 = magic(i, j + 1, last, direction);
  int ans;

  ans = Math.max(Math.max(Math.max(take_both, leave_both), leave1), leave2);
  hm.put(i + " " + j + " " + last + " " + direction, ans);
  return ans;

 }

现在上面的代码可以用于我能做的尽可能多的测试用例，但是复杂度很高。我如何降低时间复杂度，我可以在这里消除一些状态变量吗？有没有一种有效的方法来做到这一点？

Answer 1

首先让我们减少状态的数量:设f(i, j, d) 是从第一个字符串中的位置 i 开始到第一个字符串中的位置 j 的最长公共(public)之字形序列的长度第二个字符串，从方向 d(向上或向下)开始。

我们有复发

f(i, j, up) >= MAX(i' > i, j' > j : f(i', j', up))
if s1[i] = s2[j]:
    f(i, j, up) >= MAX(i' > i, j' > j, s1[i'] > x : f(i', j', down))

向下 方向类似。以直接的方式解决这个问题将导致类似 O(n⁴ · W) 的运行时间，其中 W 是数组中整数的范围。 W 不是多项式有界的，因此我们绝对希望摆脱这个因素，并且理想情况下一路上有几个 n 个因素。

要解决第一部分，您必须找到最大的 f(i', j', up)i' > i 和 j' > j。这是一个标准的标准二维正交极差最大查询。

对于第二种情况，您需要找到 i' > i, j' > j 和 s1[i'] > s1[i] 的最大值 (i', j', down)。即在矩形(i, ∞) x (j, ∞) x (s1[i], ∞)中进行范围最大查询。

现在这里有 3 个维度看起来很吓人。但是，如果我们以 i 的降序处理状态，那么我们可以摆脱一维。因此，我们将问题简化为矩形 (j, ∞) x (s1[i], ∞) 中的范围查询。坐标压缩将值的维度降低到 O(n)。

您可以使用二维数据结构，例如 range tree或二进制索引树来解决 O(log² n) 中的两种范围查询。总运行时间为 O(n² · log² n)。

您可以使用分数级联去除一个对数因子，但这与一个高常数因子相关联。运行时间仅比寻找最长公共(public)子序列的时间少一个对数因子，这似乎是我们问题的下限。