0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you're not sure that your solution works, prove that it does. That's the best way to know for sure. $\endgroup$
    – Yuval Filmus
    Commented Feb 19, 2016 at 12:25
  • $\begingroup$ @YuvalFilmus The OP has already identified that he's missing a recursive formulation and correctness proof. $\endgroup$
    – Raphael
    Commented Feb 19, 2016 at 12:41
  • 2
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Commented Feb 19, 2016 at 12:42
  • $\begingroup$ 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 ;) $\endgroup$
    – Musa Al-hassy
    Commented Apr 7, 2016 at 16:21
  • $\begingroup$ Are the $p_i$ required to be distinct? I assume so. $\endgroup$
    – Zachary Vance
    Commented Oct 12, 2020 at 4:37

1 Answer 1

Reset to default
1
$\begingroup$

A counter example where your algorithm fails: S = 0 7 1 4 6 5 3 2.

Expected : 5, your algorithm would produce 3

There is an O(n^3) dynamic programming based algorithm for this if you are interested :)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.