Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ is $x_{i_1},x_{i_2},\ldots,x_{i_k}$ in which $i_1<i_2<\ldots<i_k$ and $x_{i_1}\leq x_{i_2}\leq\ldots\leq x_{i_k}$. Can you provide an algorithm to find the Longest increasing Subsequence in an efficient way?
Asked
Active
Viewed 131 times
1
-
5Well, maybe the correct answer is "No" for some :) – Hagen von Eitzen Dec 13 '14 at 16:08
-
1You should rewrite the question using LaTeX so it can be found by searching. – Henrik supports the community Dec 13 '14 at 16:11
-
1Have you tried Googling "Longest Increasing Subsequence"? This is a really famous problem, and it's typically solved using Dynamic Programming. – apnorton Dec 13 '14 at 16:11