We show that any deterministic data-stream algorithm that makes a
constant number of passes over the input and gives a constant factor
approximation of the length of the longest increasing subsequence in a
sequence of length $n$ must use space $\Omega(\sqrt{n})$. 
This proves a conjecture made by Gopalan, Jayram, Krauthgamer and Kumar.
Our results yield asymptotically tight lower bounds for all approximation 
factors. Our proof is based on analyzing a related communication problem
and proving a direct sum type property for it.