algorithm - 找到从头到尾最长的递增子序列

Question

如何找到 LIS,subsequence 以及我不能跳过第一个和最后一个元素的约束？

编辑：我的真正意思是我必须从头开始并在最后结束。另外我想将它扩展为之字形子序列，如 动态编程：查找最长的子序列即之字形

Answer 1

实现典型的 LIS 算法，只需从输入中删除所有小于第一个元素和大于最后一个元素的元素。只考虑不是解决方案的第一个或最后一个元素，然后将这两个附加到您找到的解决方案中。此外，如果最后一个元素不大于第一个元素，则表示没有增加的子序列。