algorithm - 在附加条件下查找数组中可能的序列数

Question

有一个序列{a1, a2, a3, a4, ..... aN}。运行是序列的最大严格递增或严格递减连续部分。例如。如果我们有一个序列 {1,2,3,4,7,6,5,2,3,4,1,2} 我们有 5 种可能的运行 {1,2,3,4,7}, {7, 6,5,2}、{2,3,4}、{4,1} 和 {1,2}。

给定四个数N、M、K、L，统计N个数的可能序列的个数正好有M个游程，序列中的每个数都小于或等于K，相邻数之间的差为小于等于L

这个问题是在采访中被问到的。

我只能想到蛮力解决方案。 这个问题的有效解决方案是什么？

Answer 1

使用动态规划。对于子串中的每个数字，分别维护最大递增和最大递减子序列的计数。当您将新号码递增添加到末尾时，您可以使用这些计数来更新新号码的计数。复杂度:O(n^2)