增加递减顺序 [英] increasing decreasing sequence

问题描述

一个序列中的元素首先减少的值，然后增加被称为V-序列。在一个有效的V-序列应该有向上升臂下降和至少一个元素的至少一种元素。

A sequence in which the value of elements first decrease and then increase is called V- Sequence. In a valid V-Sequence there should be at least one element in the decreasing and at least one element in the increasing arm.

例如，5 3 1 9 17 23是具有在减少臂即5和3中增加臂即9，17及23的两个元素，和3个元素的有效的V-序列。但没有序列6 4 2或8 10 15的垂直序列，因为6 4 2有，而8 10 15已在减少部分没有元素的增加部分不元素。

For example, "5 3 1 9 17 23" is a valid V-Sequence having two elements in the decreasing arm namely 5 and 3, and 3 elements in the increasing arm namely 9, 17 and 23 . But none of the sequence "6 4 2" or "8 10 15" are V-Sequence since "6 4 2" has no element in the increasing part while "8 10 15" has no element in the decreasing part.

给定的序列N个数的发现其最长（不一定是连续的）的子序列，其是V型？

Given a sequence of N numbers find its longest (not necessarily contiguous) sub-sequence which is a V-Sequence ?

是否有可能做到这一点的为O（n）/ O（LOGN）/ O（N ^ 2）？

Is it possible to do this in O(n)/O(logn)/O(n^2) ?

推荐答案

该解决方案是相当类似的时间最长的非递减子序列的溶液中。所不同的是现在每个元素需要存储两个值 - 什么是最长V序列从这个元素开始的长度和什么是最长递减子序列起始于这个的长度。请看看在典型的非递减序列的解决方案，我认为这应该是一个好足够多的小费。我相信你能达到最好的复杂度为O（N *的log（n）），但复杂度为O溶液（N ^ 2）是比较容易实现的。

The solution is quite similar to the solution of the longest-non-decreasing subsequence. The difference is that now for each element you need to store two values - what is the length of the longest V sequence starting from this element and what is the length of the longest decreasing subsequence starting at this. Please take a look at the solution of the typical non-decreasing subsequence solution and I believe this should be a good enough tip. I believe the best complexity you can achieve is O(n*log(n)), but a solution of complexity O(n^2) is easier to achieve.

希望这有助于。

这篇关于增加递减顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！