How to find longest constrained subsequence

Question

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

1. the start element of the subsequence is the smallest of the subsequence.
2. the end element of the subsequence is the largest of the subsequence.

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

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

Here is a O(N^2) algorithm:

• 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.

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

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

Answer 1

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

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.

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 |
              |       +----+
              |       |    |

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.

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());
    }
}