最长的子序列增加，使LIS中的最后一个元素是最大的

Question

如何找到最长增加的子序列的最后一个和第一个元素之间的差异，以使LIS中的值（最后一个元素 - 第一个元素）最大？

<</p>

Answer 1

让我们使用标准动态编程解决方案，我们将f[i]定义为i-th元素中最长增加的子序列。我们可以为每个i存储一对(max length, smallest first element)。可以证明它会导致正确的全局解决方案（直观地，它是正确的，因为它仍然为所有子序列中的所有子序列存储一个最佳解决方案，并且一个前缀比另一种前缀是"更好"更好）。

，如果性能要求很高，则可以通过将此对存储在有效的数据结构中（如段树）来使其成为O(N log N)。

Answer 2

非常天真的算法如下：

1. 在第一张通过中找到所有最大连续子序列，其长度保持最大长度（只要维护此数字）。
2. 在第二次通过中，找到所有最大长度序列的开始和结束差异，并输出所有序列中最大的序列。

所有这些都是在o（n）中，可以在一个通行证中进行。只是为了简化它，我将其分解为两个步骤。