  Longest common subsequence ($\mathsf{LCS}$) is a classic and central problem
in combinatorial optimization. While $\mathsf{LCS}$ admits a quadratic time
solution, recent evidence suggests that solving the problem may be impossible
in truly subquadratic time. A special case of $\mathsf{LCS}$ wherein each
character appears at most once in every string is equivalent to the longest
increasing subsequence problem ($\mathsf{LIS}$) which can be solved in
quasilinear time. In this work, we present novel algorithms for approximating
$\mathsf{LCS}$ in truly subquadratic time and $\mathsf{LIS}$ in truly sublinear
time. Our approximation factors depend on the ratio of the optimal solution
size over the input size. We denote this ratio by $\lambda$ and obtain the
following results for $\mathsf{LCS}$ and $\mathsf{LIS}$ without any prior
knowledge of $\lambda$.
  $\bullet$ A truly subquadratic time algorithm for $\mathsf{LCS}$ with
approximation factor $\Omega(\lambda^3)$.
  $\bullet$A truly sublinear time algorithm for $\mathsf{LIS}$ with
approximation factor $\Omega(\lambda^3)$.
  Triangle inequality was recently used by [Boroujeni, Ehsani, Ghodsi,
HajiAghayi and Seddighin SODA 2018] and [Charkraborty, Das, Goldenberg, Koucky
and Saks FOCS 2018] to present new approximation algorithms for edit distance.
Our techniques for $\mathsf{LCS}$ extend the notion of triangle inequality to
non-metric settings.
