The longest commonly positioned increasing subsequences problem

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let and be two input sequences. Let be a subsequence of A and be a subsequence of B such that , and and () are commonly positioned (have the same index ) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with time to compute the LCPIS, where . And we also show a dual relationship between the LCPIS problem and the LCIS problem.