  Given a sequence of integers, we want to find a longest increasing
subsequence of the sequence. It is known that this problem can be solved in
$O(n \log n)$ time and space. Our goal in this paper is to reduce the space
consumption while keeping the time complexity small. For $\sqrt{n} \le s \le
n$, we present algorithms that use $O(s \log n)$ bits and $O(\frac{1}{s} \cdot
n^{2} \cdot \log n)$ time for computing the length of a longest increasing
subsequence, and $O(\frac{1}{s} \cdot n^{2} \cdot \log^{2} n)$ time for finding
an actual subsequence. We also show that the time complexity of our algorithms
is optimal up to polylogarithmic factors in the framework of sequential access
algorithms with the prescribed amount of space.
