algorithm - 序列跟随百分比

Question

问题陈述:一个人必须按顺序前往一组位置:Seq: L1 L2 L3 L4 L5 L6(假设L1、L2为位置)

但他跟随的顺序不同:实际序列:L3 L1 L2 L4 L5 L6

现在我需要找出后面的 % 序列是什么。请记住，算法应该考虑 L4、L5、L6 仍然在 L3 之后。所以这不是一个简单的%问题。

非常感谢任何帮助

Answer 1

这是一个称为 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%