algorithm - 数组的最长递增数子序列

Question

我们在类(class)中遇到了这个问题，与我交谈过的人都没有解决它。我想寻求帮助。那么问题来了:

令 A 为长度为 n 的数组，其中包含 n 个数字(数字介于 0-9 之间)。 A的数字子序列是一个正数序列，当序列中某个数的所有数字都出现在A中的一行时，它们的数字组成A的子序列。 p>

例如:序列13,1,345,89,23是输入数组A的一个数字子序列: [1,3,5,1,2,3,4, 5,8,9,4,5,2,3]

数字子序列的长度是其中出现的数字的数量(在上面的例子中:5) 如果序列中的每个数字都大于它前面的数字，则数字子序列递增。

要求在动态规划方法(基于递归公式)中找到一种算法，找到输入数组 A 的最长递增数字子序列。

提前感谢所有帮助者!

Answer 1

查看数组中的第一个数字。该数字不是您的数字序列中数字的一部分，或者是。如果是，则该数字可能有 1、2、...、n 位数字。对于每个猜测，返回:

• 不是数字:返回f(array[2...n], -1)
• 一位数的第一位:返回array[1] union f(array[2...n], number(array[1]))
• 2位数字的第1位:返回array[1...2] union f(array[3...n], number(array[1...2]))
• 三位数的第一位:返回array[1...3] union f(array[4...n], number(array[1...3]))
• ...
• n位数字的第1位:返回array[1...n]

您可以在此处进行一些优化以跳过一些步骤。

• f(array[1...k], x) = f(array[1...k], y)如果给定假设的最后一个数字，则序列中下一个数字的最小选择 x和 y是一样的。所以，如果下一个数字的最小选择array[1...k]与 x 相同和 y ，我们已经计算了 f 的值对于 x ，我们可以将该值重新用于 y .

• f(array[1...k], x) = c + f(array[2...k], x)每当array[1] = 0 , 其中c = 1如果x < 0和 c = 0如果x >= 0 .也就是说，我们可以忽略前导零，但数组开头的前导零除外，它应该始终被选为我们的第一个一位数。

• 在决定一个数字是否是 k 的第一位数字时-digit 数字，如果你从不选择前导零，你就会知道序列中剩余数字的上限由 n/k 给出。 ，因为在此之后选择的任何数字都需要至少为 k数字长。如果您还记得迄今为止看到的最长序列，您可以识别出没有希望比您看到的更好的路径并忽略它们。

• 如果一个数组至少有 k(k+1)/2里面有非零数字，至少有一个长度为k的数列通过从左到右依次取具有 1, 2, ..., k 个非零数字的数字获得。因此，如果您预先计算这个值，您可能会立即避开一些路径。

这是经过讨论的优化的粗略伪代码:

solve(array[1...n])

    z = number of non-zero entries in array
    last_number = -1
    min_soln = floor((sqrt(1 + 8z) - 1) / 2)
    return solve_internal(array[1...n], min_soln, last_number)



memo = {}

solve_internal(array[1...n], min_soln, last_number)

    // ignore potentially leading zeroes except the first one
    if array[1] = 0 then
        if last_number < 0 then
            return {0} union solve_internal(array[2...n], min_soln - 1, 0)
        else then
            return solve_internal(array[2...n], min_soln, last_number)

    // abort since we don't have enough digits left to get a solution
    if floor(n / #digits(last_number)) < min_soln return []

    // look up current situation in previous partial solutions
    z = smallest number formable in array greater than last_number
    if memo contains (n, z) then
        return memo[n, z]

    soln = {}
    for k = 1 to n do
        soln_k = solve_internal(array[k+1...n], min_soln - 1, array[1...k])
        if |soln_k| > |soln| then
            soln = soln_k
            min_soln = |soln|

    memo[n, z] = soln
    return soln