Before revision:  We then use it to construct a nonadaptive algorithm with query complexity O(r  /\lambda ^2) that, for an array in which the LIS is of length at least \lambda n, outputs a O (\lambda) multiplicative approximation to the length of the LIS . Our algorithm improves upon state of the art nonadaptive algorithms for LIS estimation (for r=n) in terms of approximation guarantee.
After revision:  We then use it to construct a nonadaptive algorithm with query complexity O(r /\lambda )) that, for an array in which the LIS is of length at least \lambda n, outputs a O (\lambda) multiplicative approximation to the length of the LIS . Our algorithm improves upon state of the art nonadaptive algorithms for LIS estimation (for r=n) in terms of approximation guarantee.