c - 算法 : Unimodal Streak

Question

我有这个算法问题要解决，我有一个带数字的 vector ，我必须找到最长的单峰条纹(这意味着它可以增加然后减少，但不能超过一次)。

即:在 vector [4 5 8 5 9 6 3] 中，45863 是单峰条纹，而 458593 不是，因为它增加到 8 然后减少到 5 然后再次增加(这是不允许的)。

使用动态规划，我设法创建了 3 个 vector :第一个具有在元素 x 处停止的最长上升条纹的长度，第二个具有从元素 x 开始的最长下降条纹的长度，第三个是前两个的总和。

基本上，如果我取第三个 vector 的最大值，它就是最长单峰条纹的长度+1(因为元素 x 被计算了两次)。

我现在要做的是显示那条连胜记录。我正在考虑以这种方式使用这些 vector :使用“for”从最大值的位置开始并到达 vector 的开头。我将检查第一个 vector 中的值，如果该值恰好比前一个值小 1(第一次它将是第一个 vector 中最大值的值)，我将将该值保留在队列中稍后显示，然后继续。然后，我将使用第二个 vector 对 vector 的第二部分做几乎相同的事情。

我知道这听起来很困惑和复杂，但通过这个例子它会更清楚。

I have this base vector :  
9 4 5 6 9 7 8 3 4 3

1 1 2 3 4 4 5 1 2 1 (first vector) = A
4 2 3 3 4 3 3 1 2 1 (second vector) = B
5 3 5 6 8 7 8 2 4 2 (sum of the two) = C

所以这里最长的连胜是 7，峰值是 9(或 8，但那是一样的)。

所以我想做的是:第一个 vector 中峰值的值为“4”，所以我将检查第一个向左的“3”，它是 6，我将其放入队列中，我现在正在寻找第一个“2”是队列中的5，然后是4，因为它是第一个值为“1”的。

然后我将显示队列，然后是峰值，然后对第二部分做同样的事情。我将有 4 5 6 9 7 4 3。(这是好的顺序)。

我的问题是:这每次都能奏效吗？我觉得有些事情可能会搞砸，所以我做了一些测试，每次都很好。我想知道是否有特定的基本 vector 把事情搞砸了。如果可以，请告诉我您的想法，那就太好了!

感谢您阅读所有这些内容，希望有人能帮助我。

Answer 1

我觉得不错。如果正确实现，动态规划解决方案可以保证找到最佳方案，因为它会间接检查所有可能的选择。在这种情况下，序列需要有一个“中心”(它停止增加并开始减少的点)。那就是您要强制执行的参数。

但请注意

The I'm going to check the value in the first vector and if that value is exactely 1 less than the previous value (the first time it will be the value of the maximum in the first vector) I will keep that value in a queue and display it later.

我认为您在这里真正想要的是堆栈，而不是队列，因为您找到的最后一个元素就是您要显示的第一个元素。这适用于第一个 vector 。

更一般地说，您可以使用常规数组，这对两个 vector 都有效。