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

Question

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

1. 子序列的start元素是子序列中最小的.
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],我们可以得到满足约束的长度为zY [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) 算法。

将输入序列的元素解释为 2D 中的点，其中 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, x'] 中的 x'' （注意在这种情况下 y'' <= y'），我们需要在最小点处增加线段树其 x 坐标位于]inf, x'']，y 坐标位于]inf, y'']。这看起来可能不是一维的，但实际上，对于极小点，x 坐标上的排序和 y 坐标上的排序是相反的，因此这组键是一个区间。类似地，给定一个点 (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());
    }
}