# Longest double increasing subsequence (LIS variant)

Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $2<i\leq k$ we have $p_{i-2} < p_i$. For example, if $S = 1 \space 4\space 2\space 7\space 1\space 6$, a possible double increasing subsequence is $P = 1\space 2\space 7\space 6$ because $7 > 1$ and $6 > 2$. (For every sequence $S$ with more than 2 elements, there's a trivial subsequence of length 2) The problem is to determine the length of longest double increasing subsequence (LDIS) of a given series of integers, $S$.

This is what I've done: I defined $C[i]$ to be the length of the LDIS of the series that ends with $s_i$, and $E[i]$ to be the element before the last element of the LDIS that ends with $s_i$. In the example aforementioned, $C[6] = 5$, and $E[6]=7$. If there are several options for $E[i]$, we'll take the minimal one. For example for $C[5] = 2$ we have 3 different options for LDIS, all of lengths 2: $4 \space 1$, $2 \space 1$ and $7 \space 1$ (Trivial LDIS's), so we'll define $E[5] = 2$.

Now my dynamic programming solution is just like LIS solution (the $n^2$, not the $nlogn$):
If $C$ and $E$ are my $n$-sized arrays, $C[1] = 1, E[1] = \inf$(meaning there's no previous value), $C[2]=2,E[2]=s_1$, and for every $2<i\leq n$ we finding $C[i]$ by iterating over the previous $i$ calculates values, and we take the maximum over the $C[i]$'s such that $s_i>E[i]$, plus 1. (Again, if there are several candidates, we take E[i] as the minimal of the possible options) After calculating all $n$ values, we iterate over the array and choose the index that hold the maximal $C[i]$.

This is my mind set in general, maybe I've missed several details but I believe I delivered the idea. Now these are my problems with my solution:
1) It misses strong, well defined recursive formula. I can phrase some sort of recursive relation according to the regularity of the question, but it feels kinda forced. (Despite of the iterative solution I've describe, which is fairly simple)
2) I've ran the algorithm on several examples and it seems to give a right answer, but as a consequence of 1, I have hard time "believing" my solution is correct. I feel like there's more simple and elegant solution to the problem.

Any ideas will be vastly appreciated, thanks in advance.

• If you're not sure that your solution works, prove that it does. That's the best way to know for sure. – Yuval Filmus Feb 19 '16 at 12:25
• @YuvalFilmus The OP has already identified that he's missing a recursive formulation and correctness proof. – Raphael Feb 19 '16 at 12:41
• Do you have any specific question about either 1) or 2)? As it is, your post is a status report, not a question. What have you tried towards a recursive formulation and a correctness proof? – Raphael Feb 19 '16 at 12:42
• You say you've "ran the algorithm" and are looking for a "recursive formula", if you provide the algorithm code explicitly, perhaps we can be of use in providing the formula ;) – Musa Al-hassy Apr 7 '16 at 16:21
• Are the $p_i$ required to be distinct? I assume so. – Zachary Vance Oct 12 '20 at 4:37