问题陈述:一个人必须按顺序前往一组位置: Seq:L1 L2 L3 L4 L5 L6(假设L1、L2是位置)
但是他按照不同的顺序去了不同的地点: 实际序列:L3 L1 L2 L4 L5 L6
现在我需要找出后面的 % 序列是什么。请记住，该算法应考虑 L4、L5、L6 仍然在 L3 之后。所以这不是一个简单的%问题。
非常感谢任何帮助
最佳答案
这是一个名为 Longest Increasing Subsequence 的问题并且有 O(n log n) 算法。
要找到百分比，您只需找到 LIS(V)/length(V)。
以下是 Python 中的示例实现 (O(n^2))
编辑:更改代码以明确指出 O(n) 步骤可以变成 O(log n)
def LIS(V):
n = len(V)
T = [0]*(n+1)
L = 0
for i in xrange(n):
#this step can be a binary search
j = max(j for j in xrange(L+1) if j==0 or V[T[j]] < V[i])
T[j+1] = i
L = max(L, j+1)
return L/float(n)*100
print '{:.2f}%'.format(LIS([3, 1, 2, 4, 5, 6])) #83.33%
print '{:.2f}%'.format(LIS([1, 2, 3, 4, 5, 6])) #100.00%
print '{:.2f}%'.format(LIS([6, 1, 2, 5, 4, 3])) #50.00%
关于algorithm - 序列跟踪百分比，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29957231/