Question

What is the expected length of the longest consecutive subsequence of a random permutation of the integers 1 to N? To be more precise we are looking for the longest string of consecutive integers in the permutation (disregarding where this string occurs). I believe the answer should be ~ c ln(n), but I have been unable to prove this.

Update: We are looking for the longest increasing subsequence. This is to say 9,1,5,2,7,3 has an increasing subsequence 1,2,3.