arrays - 如何找到最长的约束子序列

Question

给定一个包含 N 个不同整数的数组，找到满足以下条件的最长子序列:

1. 子序列的起始元素是子序列中最小的。
2. 子序列的末尾元素是子序列中最大的。

例如:8、1、9、4、7。答案是 1,4,7。

2,6,5,4,9,8。答案是 2,6,5,4,9 或 2,6,5,4,8。

这是一个O(N^2)算法:

• 让X是数字数组。
• 遍历 X .假设我们在索引 i .让Y是数组，其中 Y[j] 是 (j, i] 中的元素数小于 X[j]。让z是 [j, i] 中的元素数小于 X[i]。如果X[j]小于X[i]，我们可以得到一个满足约束的长度为z-Y[j]的子序列。

• 设置z至 1 .循环 j来自 i-1下降到 0 .

  if X[j] < X[i]:
z++;
ans = max(ans, z - Y[j]);
else Y[j]++;

我们可以做得更好吗？我认为应该有一个 O(NlogN)找到最大长度的算法。

Answer 1

让我重新解释一下这个 O(n log n) 算法。

将输入序列的元素解释为二维点，其中 x 坐标是索引，y 坐标是值。我们正在寻找包含最多输入点的矩形，受左下角和右上角为输入点的约束。在通常的分量偏序下，最优矩形的左下角最小，右上角最大。

进行两次线性扫描以找到最小点和最大点。创建一个由前者作为键的整数值线段树，其操作 (i) 接受键的间隔并递增/递减相关值，以及 (ii) 计算最大值。该算法是从左到右遍历最大点，使用线段树跟踪(相对于偏序)每个最小点和当前最大点之间有多少输入点。

当我们从左向右移动时，最小值和最大值都会下降。那么，假设我们正从一个最大值点 (x, y) 移动到下一个最大值点 (x', y')。我们有 x < x' 和 y' < y。线段树中的值如何变化？由于x < x'，x坐标在]x, x']中的点不属于右上角(x, y)的矩形，但可能属于右上角(x', y')的矩形。反之，由于y' < y，y坐标在]y', y]中的点可能属于右上(x, y)的矩形，但不属于右上(x', y')的矩形。所有其他点不受影响。

----+                   empty
    |
----+---------+ (x, y)
      removed |
--------------+-------+ (x', y')
              | added |
              |       +----+
              |       |    |

我们逐一检查可能受影响的点，更新线段树。这些点按 x 排序；如果我们在初始化期间复制并按 y 排序，那么我们可以有效地枚举可能受影响的点。请注意，随着时间的推移，x 间隔成对不相交，y 间隔也是如此，因此我们可以在每个可能受影响的点上花费对数时间。给定一个点 (x'', y'') 使得 x'' in ]x, x'](注意在这种情况下 y'' <= y')，我们需要在最小点处递增线段树其 x 坐标位于 ]inf, x'']，其 y 坐标位于 ]inf, y'']。这看起来可能不是一维的，但实际上对于极小点来说x坐标上的排序和y坐标上的排序是相反的，所以这组key就是一个区间。类似地，给定一个点 (x''', y''') 使得 y''' 在 ]y', y] 中(注意在这种情况下 x''' <= x)，我们需要递减值在键的间隔。

这是 Java 中“神奇”的线段树数据结构。

public class SegmentTree {
    private int n;
    private int m;
    private int[] deltaValue;
    private int[] deltaMax;

    private static int nextHighestPowerOfTwoMinusOne(int n) {
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n;
    }

    public SegmentTree(int n) {
        this.n = n;
        m = nextHighestPowerOfTwoMinusOne(n) + 1;
        deltaValue = new int[m];
        deltaMax = new int[m];
    }

    private static int parent(int i) {
        int lob = i & -i;
        return (i | (lob << 1)) - lob;
    }

    private static int leftChild(int i) {
        int lob = i & -i;
        return i - (lob >>> 1);
    }

    private static int rightChild(int i) {
        int lob = i & -i;
        return i + (lob >>> 1);
    }

    public int get(int i) {
        if (i < 0 || i > n) {
            throw new IllegalArgumentException();
        }
        if (i == 0) {
            return 0;
        }
        int sum = 0;
        do {
            sum += deltaValue[i];
            i = parent(i);
        } while (i < m);
        return sum;
    }

    private int root() {
        return m >>> 1;
    }

    private int getMax(int i) {
        return deltaMax[i] + deltaValue[i];
    }

    public void addToSuffix(int i, int delta) {
        if (i < 1 || i > n + 1) {
            throw new IllegalArgumentException();
        }
        if (i == n + 1) {
            return;
        }
        int j = root();
        outer:
        while (true) {
            while (j < i) {
                int k = rightChild(j);
                if (k == j) {
                    break outer;
                }
                j = k;
            }
            deltaValue[j] += delta;
            do {
                int k = leftChild(j);
                if (k == j) {
                    break outer;
                }
                j = k;
            } while (j >= i);
            deltaValue[j] -= delta;
        }
        while (true) {
            j = parent(j);
            if (j >= m) {
                break;
            }
            deltaMax[j] =
                Math.max(0,
                         Math.max(getMax(leftChild(j)),
                                  getMax(rightChild(j))));
        }
    }

    public int maximum() {
        return getMax(root());
    }
}