有一个序列 {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
这个问题是在面试的时候问的。
我只能想到一种蛮力的解决方案。 这个问题的有效解决方案是什么？
最佳答案
使用动态规划。对于子串中的每个数字，分别保持最大递增和最大递减子序列的计数。当您将新数字逐渐添加到末尾时，您可以使用这些计数来更新新数字的计数。复杂度:O(n^2)