由于其中包含N个不同的整数数组，找到最长的序列中满足：

Given an array which contains N different integers, find the longest subsequence which satisfies:

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

Eg: 8,1,9,4,7. The answer is 1,4,7.

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

2,6,5,4,9,8. The answer is 2,6,5,4,9 or 2,6,5,4,8.

下面是一个 O（N ^ 2）算法：

设置以Z 到 1 。循环Ĵ从 I-1 到 0 。 Let X be the array of numbers. Iterate over X. Suppose we are at index i. Let Y be the array where Y[j] is the number of elements in (j, i] which are smaller than X[j]. Let z be the number of elements in [j, i] which are smaller than X[i]. If X[j] is smaller than X[i], we can get a subsequence of length z-Y[j] which satisfies the constrains.

Set z to 1. Loop j from i-1 down to 0.

如果X [J]＆LT; X [I]：     ž++;     ANS = MAX（ANS，Z - Y [J]）; 否则Y [J] ++;

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

我们可以做的更好？我觉得应该有一个 O（NlogN）算法找出最大长度。

Can we do better? I think there should be an O(NlogN) algorithm to find the max length.

推荐答案

让我重做此操作系统的解释（N log n）的算法。

Let me redo the explanation of this O(n log n) algorithm.

间$ P $角输入序列的如点在二维的元素，其中的x坐标是索引，和y坐标是值。我们正在寻找含有最输入点，受该左下角和右上角的输入点的约束矩形。按照通常的部件逐偏序，最佳矩形左下角是最小的，而右上角是最大的。

Interpret the elements of the input sequence as points in 2D, where the x-coordinate is the index, and the y-coordinate is the value. We're looking for the rectangle containing the most input points, subject to the constraint that the lower left corner and the upper right corner be input points. Under the usual component-wise partial order, the lower left corner of the optimum rectangle is minimal, and the upper right corner is maximal.

请两个线性扫描，找到最小和最大点。创建一个整数值线段树由前键控，与操作（ⅰ）接受键和增量的间隔/递减关联值和（二）中计算的最大值。该算法是迭代向左通过​​最大点向右，使用线段树跟踪输入点之间多少位于（相对于所述偏序）各极小点和当前最大点

Make two linear sweeps to find the minimal and maximal points. Create an integer-valued segment tree keyed by the former, with operations that (i) accept an interval of keys and increment/decrement the associated values and that (ii) compute the maximum value. The algorithm is to iterate left to right through the maximal points, using the segment tree to track how many input points lie between (with respect to the partial order) each minimal point and the current maximal point.

这两个最小点和最大点往下走，因为我们左右移动。假设，那么，我们从最大的点（x，y）的移动到下一个最大点（X'，Y'）。我们有X - LT; X'和Y'＆其中;年。如何在段树中值的变化？由于x＆LT; X'，与点x坐标中] X，X']不属于矩形与右上（X，Y），但可能属于矩形与右上（X'，Y'）。相反，由于Y'＆LT; Y，与点的y坐标中] Y'，y]的可属于矩形与右上（X，Y），但不属于矩形与右上（X'，Y'）。所有其他点都不会受到影响。

Both minimal points and maximal points go down as we move left to right. Suppose, then, that we're moving from a maximal point (x, y) to the next maximal point (x', y'). We have x < x' and y' < y. How do the values in the segment tree change? Since x < x', the points with x-coordinate in ]x, x'] do not belong to rectangles with upper right (x, y) but may belong to rectangles with upper right (x', y'). Conversely, since y' < y, the points with y-coordinate in ]y', y] may belong to rectangles with upper right (x, y) but do not belong to rectangles with upper right (x', y'). All other points are unaffected.

----+                   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）的，我们需要减小值在键的间隔

We go through the possibly affected points one by one, updating the segment tree. The points are given sorted by x; if we make a copy and sort by y during initialization, then we can enumerate the possibly affected points efficiently. Note that, over time, the x-intervals are pairwise disjoint, as are the y-intervals, so we can afford to spend logarithmic time on each possibly affected point. Given a point (x'', y'') such that x'' in ]x, x'] (note that y'' <= y' in this case), we need to increment the segment tree at the minimal points whose x-coordinate lies in ]inf, x''] and whose y-coordinate lies in ]inf, y'']. This may not look one-dimensional, but in fact, the ordering on x-coordinates and ordering on y-coordinates are opposite for minimal points, so this set of keys is an interval. Similarly, given a point (x''', y''') such that y''' in ]y', y] (note that x''' <= x in this case), we need to decrement the values at an interval of keys.

下面是Java中的神奇段树结构。

Here's the "magic" segment tree data structure in 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());
    }
}