顺序以下百分比

Question

问题陈述：一个人必须按顺序转到一组位置：顺序：L1 L2 L3 L4 L5 L6（假设 L1、L2 是位置）

但他跟着去了不同地点的顺序：实际顺序： L3 L1 L2 L4 L5 L6

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

任何帮助受到高度赞赏

Answer 1

这是一个

被称为最长递增子序列的问题，并且有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%

Answer 2

您应该考虑两个输入（初始序列和实际序列）中最长的公共子序列

将最长的公共子序列除以位置数，得到 % 序列的后跟。

在您的情况下，它是 5/6 = .8333 = 83.33%

Answer 3

我会尝试使用您的示例测试位置数组中每个连续位置之间的距离，如下所示：

distance from L1 to L2 = 1
distance from L2 to L3 = 2
distance from L3 to L4 = 3
distance from L4 to L5 = 1
distance from L5 to L6 = 1
then add them up...TTL = 8
A perfect, 100% score is 5
Our score is 8
The difference between our score and a perfect score is 8-5 = 3
The percentage is subtracted from 100% like so: 1.00 - 3/5 = 0.40 = 40%