Length of longest subsequence as a martingale Consider a sequence of continuous random variables $(X_n)_{n \geq 1}$. Let $Y_n$ denote the longest increasing subsequence in the tuple $(X_1,\dots,X_n)$. Does $Y_n$ form a martingale? If not, can I form a martingale using $Y_n$?

It is clear that $Y_n$ has finite expectation, but I do not know how is the expectation like precisely. I'm skeptical that $\mathrm{E}[Y_{n+1} - Y_n \mid X_1,\dots,X_n] = 0$. Note that since $X_n$ are all continuous, two of them are equal with probability $0$ so we can treat them to be pairwise distinct.
It is clear here that if $Y_n = k$, then $Y_{n+1} \in \{k,k+1\}$, and $Y_{n+1} = k+1$ iff the longest subsequence in $(X_1,\dots,X_n)$ lies on its tail. Surely that occurs with non-zero probability, and since $Y_n \not< k$, I doubt that $Y_n$ itself forms a martingale. I therefore suspect that $Y_n - c$ forms a martingale for some constant $c$, or possibly some slight variations, such as $Y_n - cn$.
Thanks in advance.

EDIT: As pointed out by @Nate, since $Y_n$ is non-decreasing and is not a constant, it itself can't be a martingale. My ultimate goal is to prove the following inequality:
$$
\mathrm{P}[Y_n - \mathrm{E}[Y_n] \geq t]\leq e^{-\frac{2t^2}{n}}
$$
If $Y_n$ is a martingale, then it is a very simple application of the Azuma-Hoeffding Inequality. However, this is clearly not the case, and the main problem I'm facing lies in the construction of the martingale.
 A: An extended comment: in general, there will not exist any sequence of constants $c_n$ such that $Z_n = Y_n - c_n$ is a martingale.
Suppose the $X_i$ are iid.  Let $A_{n+1}$ be the event that $X_1, \dots, X_{n+1}$ has a strictly longer increasing subsequence than $X_1, \dots, X_n$ did.  Then $Y_{n+1} - Y_n = 1$ on $A_{n+1}$, and $0$ on $A_{n+1}^c$, which is to say $Y_{n+1} - Y_n = 1_{A_{n+1}}$.  Now if $Z_n$ is a martingale then we have 
$$P(A_{n+1} \mid X_1, \dots, X_n) = E[Y_{n+1} - Y_n \mid X_1, \dots, X_n] = c_{n+1} - c_n.$$
Since the conditional probability is deterministic, we conclude $A_{n+1}$ is independent of $\sigma(X_1, \dots, X_n)$.  But this is absurd - the probability of getting a strictly longer increasing subsequence is clearly influenced by the values you already had.  For instance, if it happens that $X_1, \dots, X_n$ are all very low values, then it is very likely that $X_{n+1}$ will be greater than all of them, which will certainly add to the length of the longest increasing subsequence.
