can anyone prove this with induction?

Question

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?