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

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)中单调递减

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

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

有没有更好的办法？

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[.]后，您将遍历所有D[.]并找到最大值。这是在线性时间内完成的。