Dưới đây là triển khai bằng Python dựa trên gợi ý rất hữu ích của izomorphius ở trên. Điều này được xây dựng trên this implementation của sự cố tăng dần. Nó hoạt động bởi, như izomorphius nói, theo dõi "những gì tốt nhất V được tìm thấy cho đến nay" cũng như "các chuỗi tăng tốt nhất được tìm thấy cho đến nay". Lưu ý rằng việc mở rộng V, một khi nó đã được xác định, không khác với việc mở rộng chuỗi giảm dần. Cũng phải có một quy tắc để "đẻ trứng" ứng viên mới của V từ các chuỗi tăng ngày trước đó.
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]
Một số ví dụ đầu ra:
>>> 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]
Những con số trong dãy là theo thứ tự giống như họ đang có trong chuỗi gốc, nhưng không cần phải tiếp giáp, phải không? – gcbenison
có chính xác. Điều đó có nghĩa là bạn có thể xóa các phần tử khỏi chuỗi gốc nhưng không thể thêm và số lần xóa phải tối thiểu. –
Bản sao của http://stackoverflow.com/questions/9764512/longest-subsequence-that-first-increases-then-decreases/9764580#9764580 –