  The similarity between a pair of time series, i.e., sequences of indexed
values in time order, is often estimated by the dynamic time warping (DTW)
distance, instead of any in the well-studied family of measures including the
longest common subsequence (LCS) length and the edit distance. Although it may
seem as if the DTW and the LCS(-like) measures are essentially different, we
reveal that the DTW distance can be represented by the longest increasing
subsequence (LIS) length of a sequence of integers, which is the LCS length
between the integer sequence and itself sorted. For a given pair of time series
of length $n$ such that the dissimilarity between any elements is an integer
between zero and $c$, we propose an integer sequence that represents any
substring-substring DTW distance as its band-substring LIS length. The length
of the produced integer sequence is $O(c n^2)$, which can be translated to
$O(n^2)$ for constant dissimilarity functions. To demonstrate that techniques
developed under the LCS(-like) measures are directly applicable to analysis of
time series via our reduction of DTW to LIS, we present time-efficient
algorithms for DTW-related problems utilizing the semi-local sequence
comparison technique developed for LCS-related problems.
