Aquí hay una implementación en Python basada en la sugerencia muy útil de izomorphius anterior. Esto se basa en this implementation del creciente problema de subsecuencia. Funciona, como dice izomorphius, haciendo un seguimiento de "las mejores V encontradas hasta ahora", así como "las mejores secuencias en aumento encontradas hasta ahora". Tenga en cuenta que extender una V, una vez que se ha identificado, no es diferente de extender una secuencia decreciente. También tiene que haber una regla para "engendrar" nuevas V candidatas de subsecuencias crecientes previamente encontradas.
from bisect import bisect_left
def Vsequence(seq):
"""Returns the longest (non-contiguous) subsequence of seq that
first increases, then decreases (i.e. a "V sequence").
"""
# head[j] = index in 'seq' of the final member of the best increasing
# subsequence of length 'j + 1' yet found
head = [0]
# head_v[j] = index in 'seq' of the final member of the best
# V-subsequence yet found
head_v = []
# predecessor[j] = linked list of indices of best increasing subsequence
# ending at seq[j], in reverse order
predecessor = [-1] * len(seq)
# similarly, for the best V-subsequence
predecessor_v = [-1] * len(seq)
for i in xrange(1, len(seq)):
## First: extend existing V's via decreasing sequence algorithm.
## Note heads of candidate V's are stored in head_v and that
## seq[head_v[]] is a non-increasing sequence
j = -1 ## "length of best new V formed by modification, -1"
if len(head_v) > 0:
j = bisect_left([-seq[head_v[idx]] for idx in xrange(len(head_v))], -seq[i])
if j == len(head_v):
head_v.append(i)
if seq[i] > seq[head_v[j]]:
head_v[j] = i
## Second: detect "new V's" if the next point is lower than the head of the
## current best increasing sequence.
k = -1 ## "length of best new V formed by spawning, -1"
if len(head) > 1 and seq[i] < seq[head[-1]]:
k = len(head)
extend_with(head_v, i, k + 1)
for idx in range(k,-1,-1):
if seq[head_v[idx]] > seq[i]: break
head_v[idx] = i
## trace new predecessor path, if found
if k > j:
## It's better to build from an increasing sequence
predecessor_v[i] = head[-1]
trace_idx = predecessor_v[i]
while trace_idx > -1:
predecessor_v[trace_idx] = predecessor[trace_idx]
trace_idx=predecessor_v[trace_idx]
elif j > 0:
## It's better to extend an existing V
predecessor_v[i] = head_v[j - 1]
## Find j such that: seq[head[j - 1]] < seq[i] <= seq[head[j]]
## seq[head[j]] is increasing, so use binary search.
j = bisect_left([seq[head[idx]] for idx in xrange(len(head))], seq[i])
if j == len(head):
head.append(i) ## no way to turn any increasing seq into a V!
if seq[i] < seq[head[j]]:
head[j] = i
if j > 0: predecessor[i] = head[j - 1]
## trace subsequence back to output
result = []
trace_idx = head_v[-1]
while (trace_idx >= 0):
result.append(seq[trace_idx])
trace_idx = predecessor_v[trace_idx]
return result[::-1]
Algunos ejemplo de salida:
>>> l1
[26, 92, 36, 61, 91, 93, 98, 58, 75, 48, 8, 10, 58, 7, 95]
>>> Vsequence(l1)
[26, 36, 61, 91, 93, 98, 75, 48, 10, 7]
>>>
>>> l2
[20, 66, 53, 4, 52, 30, 21, 67, 16, 48, 99, 90, 30, 85, 34, 60, 15, 30, 61, 4]
>>> Vsequence(l2)
[4, 16, 48, 99, 90, 85, 60, 30, 4]
Los números de la subsecuencia están en el mismo orden en que están en la secuencia original, pero no tiene por qué ser contiguos, ¿verdad? – gcbenison
sí exactamente. Significa que puede eliminar elementos de la secuencia original pero no puede agregarlos y el número de eliminaciones debe ser mínimo. –
Duplicado de http://stackoverflow.com/questions/9764512/longest-subsequence-hat-first-increases-then-decreases/9764580#9764580 –