算法：单峰条纹
我有这个算法问题需要解决，我有一个带有数字的向量，我必须找到最长的单峰条纹（这意味着它可以增加然后减少，但不能超过一次）。
即：在向量 [4 5 8 5 9 6 3] 中，45863 是单峰条纹，而 458593 不是，因为它增加到 8，然后减少到 5，然后再次增加（这是不允许的）。
使用动态规划我设法创建了 3 个向量： 第一个是在元素 x 处停止的最长增加条纹的长度，第二个是从元素 x 开始的最长减少条纹的长度，第三个是前两个的总和。
基本上，如果我取第三个向量的最大值，它就是最长单峰条纹的长度+1（因为元素 x 被计算了两次）。
我现在想做的就是展示这一连胜。我正在考虑以这种方式使用这些向量：使用“for”从最大值的位置开始到向量的开头。我将检查第一个向量中的值，如果该值比前一个值恰好小 1（第一次它将是第一个向量中的最大值），我将将该值保留在队列中稍后显示，然后继续。然后，我将使用第二个向量对向量的第二部分执行几乎相同的操作。
我知道这听起来很混乱和复杂，但通过这个例子会更清楚。
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，但那是同一件事）。
所以我想做的是： 第一个向量中的峰值值为“4”，所以我将检查第一个向量向左是“3”，它是6，我将其放入队列中，我现在正在寻找第一个“2”是队列中的5，然后是4，因为它是第一个值为“1”的。
然后我将显示队列，然后是峰值，然后对第二部分执行相同的操作。 我将有 4 5 6 9 7 4 3。（这是好的顺序）。
我的问题是：这每次都有效吗？我感觉有些事情可能会搞砸，所以我做了一些测试，每次都很顺利。我想知道是否有特定的基本向量会把事情搞砸。如果可以的话请告诉我你的想法那就太好了！
感谢您阅读所有这些，我希望有人可以帮助我。
I have this algorithmic problem to resolve, I have a vector with numbers and I must find the longest unimodal streak (that means it can increase then decrease, but not more than one time).
i.e : in the vector [4 5 8 5 9 6 3], 45863 is an unimodal streak while 458593 isn't because it's increasing to 8 then decreasing to 5 then increasing again (which is not permitted).
Using dynamic programming I managed to create 3 vectors :
the first one with the length of the longest increasing streak that stops at the element x, the second one with the length of the longest decreasing streak that starts at the element x, and the third one is the sum of the first two.
Basically if I take the maximum of the third vector it's the length of the longest unimodal streak+1 (because the element x is counted twice).
What I want to do now is to display that streak. I'm thinking of using these vectors that way : using a "for" starting at the position of the maximum and going to the beginning of the vector. 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, then continue. I will then do nearly the same thing for the second part of the vector using the second vector.
I know that sounds messy and complicated but with this example it will be clearer.
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
So the longest streak here is 7 and the peak is 9 (or 8 but thats the same thing).
So what I want to do is :
The value of the peak is "4" in the first vector so I'll check the first being "3" going left, it's 6, I put it in the queue, I'm now looking for the first "2", it's 5, in the queue, and then it's 4 because it's the first with the value "1".
I will then display the queue, then the peak, then do the same thing with the second part.
I will have 4 5 6 9 7 4 3. (Which is the good sequence).
My question is : Will this work every time? I have the feeling that something can screw up so I did some tests and every time it went fine. I'd like to know if there are specific base vectors that screw the thing up. If you could please tell me what you think that would be great!
Thank you for reading all this, I hope that someone can help me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我觉得不错。如果正确实现，动态规划解决方案一定能找到最优方案，因为它间接检查所有可能的选择。在这种情况下，序列需要有一个“中心”（停止增加并开始减少的点）。这就是你暴力破解的参数。
不过有一点要说的是
我认为您真正想要的是一个堆栈，而不是队列，因为您找到的最后一个元素是您想要显示的第一个元素。这适用于第一个向量。
更一般地说，您可以使用常规数组，这对两个向量都适用。
Looks good to me. The dynamic programming solution, if implemented correctly, is guaranteed to find the optimum because it indirectly checks all possible selections. In this case, the sequence needs to have a "center" (the point where it stops increasing and starts decreasing). That's the parameter you're brute-forcing.
One remark, though
I think what you really want here is a stack, not a queue, given that the last element you'll find is the first one you want to display. That applies to the first vector.
More generally, you can use a regular array and that'll work for both vectors.
我认为这是合理的。如果最佳单峰条纹的最大元素是
e，那么最佳的左半部和右半部将在A和B中找到。由于左右序列完全独立，因此该方法始终有效。I think it's sound. If the maximum element of the best unimodal streak is
e, then the best possible left half and right half will be found inAandB. Since the left and right sequences are totally independent, this method will always work.