algorithm - Find the longest increasing subsequence from start to end

Question

How do I find the LIS,subsequence, with the constraint that I cant skip first and last element?

EDIT: What I actually meant was that I have to start from the beginning and end at the end.Also I want to extend this for a zigzag subsequence like Dynamic programming: Find longest subsequence that is zig zag

Answer 1

典型的な LIS アルゴリズムを実装し、最初の要素よりも小さく、最後の要素よりも大きいすべての要素を入力から単純に削除します。ソリューションの最初または最後の要素ではない要素のみを考慮し、これら 2 つを見つけたソリューションに追加します。また、最後の要素が最初の要素よりも大きくない場合、増加する部分列はないと言います。