Suppose a[] and b[] are finite sequences of integers in which there are no pairs a[i] = a[j] or b[i] = b[j] for (i != j). Then, a[] and b[] are called weak twins if for all i, a[i] < a[i+1] iff b[i] < b[i+1] (which implies, a[i] > a[i+1] iff b[i] > b[i+1]).
Suppose s[] is again some finite sequence of integers with pairwise distinct values. The twin-width of s[] is the length of the maximum pair of disjoint subsequences a[], b[] of s[] such that a[] and b[] are weak twins.
For example, the twin-width of the sequence [1, 4, 6, 5, 3, 2] is 3 because we can extract the two following subsequences from this sequences which are weak-twins: [1, 3, 2] and [4, 6, 5].
It is clear that the twin-width of a sequence of length 2n is at most n, but in many cases, it can be much smaller.
Given a sequence s[], how can we find its twin-width?
I have tried a simple dynamic programming approach where dp[i, j] represents the length of the longest pair of weak twin subsequences which end in s[i] and s[j] respectively. To compute dp[i, j], I want to see whether all sequences ending at i', j' for i' < i and j' < j can be extended or not. Unfortunately, it appears that this approach does not seem to work since we do not know that the sequence we are extending already contains s[i] or s[j].
I am thinking of this as a slight generalization of the longest increasing sequence problem. So, maybe there is a better algorithm?