I'll start with the definitions:
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.