We present algorithms and lower bounds for the Longest Increasing
Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the
data-streaming model. To decide if the LIS of a given stream of
elements drawn from an alphabet \alphabet has length at least $k$, we
discuss a one-pass algorithm using $O(k \log \alphabetsize)$ space,
with update time either $O(\log k)$ or $O(\log \log \alphabetsize)$;
for $\alphabetsize = O(1)$, we can achieve $O(\log k)$ space and
constant-time updates. We also prove a lower bound of $\Omega(k)$ on
the space requirement for this problem for general alphabets
$\alphabet$, even when the input stream is a permutation of
$\alphabet$. For finding the actual LIS, we give a
$\ceil{\log(1+1/\eps)}$-pass algorithm using $O(k^{1+\eps}\log
\alphabetsize)$ space, for any $\eps > 0$. For LCS, there is a
trivial $\Theta(1)$-approximate $O(\log n)$-space streaming algorithm
when $\alphabetsize = O(1)$. For general alphabets $\alphabet$, the
problem is much harder. We prove several lower bounds on the LCS
problem, of which the strongest is the following: it is necessary to
use $\Omega(n/\rho^2)$ space to approximate the LCS of two $n$-element
streams to within a factor of~$\rho$, even if the streams are
permutations of each other.