arrays - How to find longest constrained subsequence -

given array contains n different integers, find longest subsequence satisfies:

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

eg: 8,1,9,4,7. answer 1,4,7.

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

here o(n^2) algorithm:

• let x array of numbers.
• iterate on x. suppose @ index i. let y array y[j] number of elements in (j, i] smaller x[j]. let z number of elements in [j, i] smaller x[i]. if x[j] smaller x[i], can subsequence of length z-y[j] satisfies constrains.

• set z 1. loop j i-1 down 0.

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

can better? think there should o(nlogn) algorithm find max length.

let me redo explanation of o(n log n) algorithm.

interpret elements of input sequence points in 2d, x-coordinate index, , y-coordinate value. we're looking rectangle containing input points, subject constraint lower left corner , upper right corner input points. under usual component-wise partial order, lower left corner of optimum rectangle minimal, , upper right corner maximal.

make 2 linear sweeps find minimal , maximal points. create integer-valued segment tree keyed former, operations (i) accept interval of keys , increment/decrement associated values , (ii) compute maximum value. algorithm iterate left right through maximal points, using segment tree track how many input points lie between (with respect partial order) each minimal point , current maximal point.

both minimal points , maximal points go down move left right. suppose, then, we're moving maximal point (x, y) next maximal point (x', y'). have x < x' , y' < y. how values in segment tree change? since x < x', points x-coordinate in ]x, x'] not belong rectangles upper right (x, y) may belong rectangles upper right (x', y'). conversely, since y' < y, points y-coordinate in ]y', y] may belong rectangles upper right (x, y) not belong rectangles upper right (x', y'). other points unaffected.

----+                   empty     | ----+---------+ (x, y)       removed | --------------+-------+ (x', y')               | added |               |       +----+               |       |    | 

we go through possibly affected points 1 one, updating segment tree. points given sorted x; if make copy , sort y during initialization, can enumerate possibly affected points efficiently. note that, on time, x-intervals pairwise disjoint, y-intervals, can afford spend logarithmic time on each possibly affected point. given point (x'', y'') such x'' in ]x, x'] (note y'' <= y' in case), need increment segment tree @ minimal points x-coordinate lies in ]inf, x''] , y-coordinate lies in ]inf, y'']. may not one-dimensional, in fact, ordering on x-coordinates , ordering on y-coordinates opposite minimal points, set of keys interval. similarly, given point (x''', y''') such y''' in ]y', y] (note x''' <= x in case), need decrement values @ interval of keys.

here's "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;         return (i | (lob << 1)) - lob;     }      private static int leftchild(int i) {         int lob = & -i;         return - (lob >>> 1);     }      private static int rightchild(int i) {         int lob = & -i;         return + (lob >>> 1);     }      public int get(int i) {         if (i < 0 || > n) {             throw new illegalargumentexception();         }         if (i == 0) {             return 0;         }         int sum = 0;         {             sum += deltavalue[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 || > 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;             {                 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());     } }