Let me repeat the explanation of this algorithm O (n log n).
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 are looking for a rectangle containing most of the input points, subject to the restriction that the lower left corner and upper right corner are input points. In the usual partial order in parts, the lower left corner of the optimal rectangle is minimal, and the upper right corner is maximum.
Take two linear sweeps to find the minimum and maximum points. Create a segment tree with integer values, introduced first, with operations that (i) take a key spacing and increase / decrease related values and (ii) calculate the maximum value. The algorithm consists of repeating from left to right through the maximum points, using the segment tree to track how many input points lie between (relative to the partial order) of each minimum point and the current maximum point.
Both minimum points and maximum points are omitted as we move from left to right. Suppose we move from the maximum point (x, y) to the next maximum 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 the x-coordinate in] x, x'] do not belong to the rectangles with the upper right (x, y), but can belong to the rectangles with the upper right (x ', y'). Conversely, since y 'y, the points with the y-coordinate in] y', y] can belong to the rectangles with the upper right (x, y), but do not belong to the rectangles with the upper right (x ', y'). All other items are not affected.
----+ empty | ----+---------+ (x, y) removed | --------------+-------+ (x', y') | added | | +----+ | | |
We go through the affected points one by one, updating the segment tree. Points are specified sorted by x; if we make a copy and sort by y during initialization, then we can efficiently list the possible points affected. Please note that over time x-intervals do not intersect in pairs, as well as y-intervals, so we can allow us to spend logarithmic time on every possible affected point. Given a point (x '', y '') such that x '' in] x, x '] (note that y' '<= y' in this case), we need to increase the segment tree at the minimum point whose x-coordinate lies in] inf, x "'] and the y-coordinate of which lies in inf, y" ”]. This may not look one-dimensional, but in fact ordering by x coordinates and ordering by y-coordinates are opposite for minimum points, so this set of keys is an interval. In the same way, given the point (x '', y '' ') such that y' '' in] y ', y] (note that x' '' <= x in this case), we need to reduce values in the key range.
Here's the magic 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()); } }