最長增加子序列，使得LIS中的最後一個元素最大

Question

如何找出最長增加子序列的最後一個和第一個元素之間的差異，使得LIS中的（最後一個元素 - 第一個元素）的值是最大 ？

Answer 1

讓我們使用標準的動態規劃解決方案，其中我們將f[i]定義爲i-th元素中結尾最長的子序列。我們可以爲每個i儲存一對(max length, smallest first element)。人們可以證明它導致了一個正確的全局解決方案（直觀地說，它是正確的，因爲它仍然存儲了針對以特定元素結尾的所有子序列的最佳解決方案，並且事實上一個前綴比另一個意味着總體子序列「更好」更好）。

如果性能要求很高，您也可以通過將這些對存儲在高效的數據結構（如分段樹）中使其成爲O(N log N)。

Answer 2

很天真的算法如下：

1. 在第一次找到所有最大連續子序列和它們的長度保持最大長度（只是保持這個數）。
2. 在第二遍中找到所有最大長度序列的開始和結束的差異，並輸出它們中最大的一個。

所有這一切都在O（n）中，可以一次完成。爲了簡化它，我將其分解爲兩個步驟。