子序列问题

最长上升子序列（LIS，Longest Increasing Subsequence）

“给定n个整数 A1， A2，… ，An，按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变）。例如序列1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，但前者更长。选出的上升子序列相邻元素不能相等”——《算法竞赛入门经典》

（部分解法灵感来源于洛谷题解）