查找從頭到尾的最長增長子序列

如何找到LIS子序列，以及不能跳過第一個和最後一個元素的約束？查找從頭到尾的最長增長子序列

編輯：我實際上的意思是，我必須從一開始和結束在end.Also開始我要像 Dynamic programming: Find longest subsequence that is zig zag

2013-02-05 marti

的曲折子擴展這個工具的典型LIS算法，簡單地刪除比第一個元素小的所有元素，並且比輸入中的最後一個元素大。只考慮不是解決方案的第一個或最後一個元素，然後將這兩個添加到您找到的解決方案中。如果最後一個元素不比第一個元素大，說明沒有增加的子序列。

來源

2013-02-05 08:09:51

哇，這是快速和正確的！現在如何用這個相同的約束來擴展這個曲折的LIS（http://stackoverflow.com/questions/6914969/dynamic-programming-find-longest-subsequence-that-is-zig-zag?rq=1）？ – marti

@marti我已經解決了SRM上的原始問題:)不幸的是，它不會很容易適應我提出的用於曲折序列的解決方案。如果不考慮從第一個元素開始的序列，並且只有在最後一個元素結束時才計算有效解，那麼您將不得不使DP更復雜一些。 –

謝謝伊瓦洛！我怎麼做？ – marti

查找從頭到尾的最長增長子序列

回答

相關問題