algorithm - 最长单调递减子序列，不包含连续元素

Question

例如:

s = <6, 5, 4, 3, 2, 1>, s1 = <6, 4, 1>, s2 = <5, 2>, s3 = <5, 3, 2>

给定 s 作为序列，s1 和 s2 是要考虑的有效子序列，但是 s3不是因为它包含一个连续的元素3和2。

如何找到最长的这样一个子序列，使其在 O(n^2) 中单调递减

我知道包含单调增加/减少的问题版本。

但是这里的附加条件让它变得困难。

一个简单的解决方案是从 i = n'th 元素以及 j = (n-1)'th 元素开始，求解就像求解对于最长的单调递减子序列，考虑到下一个元素分别位于 (i-2)th 和 (j-2)th 并比较两者的长度结尾。这仍然会给出 O(n^2)，但看起来太微不足道了。

有没有更好的方法？

Answer 1

D[i] = max { D[j] + 1 | a[i] < a[j], j < i + 1 } U {1} 

说明:对于每个元素 a[i]，您的动态规划 (DP) 检查所有在它之前且具有较低值但不相邻的数字 - 如果可以使用新数字扩展最佳序列。此外，您还可以选择开始一个新的序列(这就是 {1} 开始播放的时候)。

例子: S = <6, 0, 5, 8, 4, 7, 6 >

D[1] = max { 1 } = 1  // sequence = <6>
D[2] = max {1} = 1  // sequence = <0>
D[3] = max {1, D[0] + 1 } = 2  // sequence = <6, 5>
D[4] = max {1} = 1  // sequence = <8>
D[5] = max{D[3] + 1, D[1] + 1, 1} = 3 // sequence = <6, 5, 4>
D[6] = max{D[4] + 1, 1} = 2  // sequence = <8, 7>
D[7] = max{D[4] + 1, 1} = 2  // sequence = <8, 6>

该算法在 O(n^2) 中运行，因为计算 D[i] 需要 O(i) 时间。从等差级数的和，这个总和为 O(n^2) 来计算所有。

当您完成所有 D[.] 的计算后，您将遍历所有这些，并找到最大值。这是在线性时间内完成的。