6

给定一个包含 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。假设我们在 index i。设Y为数组，其中 Y[j] 是(j, i]小于 X[j] 的元素数。设为小于 X[i]z的元素个数。[j, 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)算法来找到最大长度。

4

1 回答 1

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'' in ]x, x'] （注意在这种情况下 y'' <= y'），我们需要在最小点处增加线段树其 x 坐标位于 ]inf, x''] 并且其 y 坐标位于 ]inf, y'']。这可能看起来不是一维的，但实际上 x 坐标上的排序和 y 坐标上的排序对于最小点是相反的，所以这组键是一个区间。

这是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());
    }
}
于 2014-04-09T03:50:40.917 回答