algorithm - 给定一串数字和多个乘法运算符，可以计算出的最大数字是多少？

Question

这是我遇到的一个面试问题，我很尴尬地被它难倒了。想知道是否有人能想出答案并提供大 O 符号。

Question: Given a string of numbers and a number of multiplication operators, 
          what is the highest number one can calculate? You must use all operators

您不能重新排列字符串。您只能使用乘法运算符来计算数字。

例如String = "312" , 1 个乘法运算符

您可以执行 3*12 = 36 或 31*2= 62。后者显然是正确的答案。

Answer 1

我在这里假设所需的乘法运算符数 m 以及数字字符串 s 已作为问题的一部分给出。

您可以使用 tabular method 解决此问题(又名“动态规划”)与 O(m|s|²) 的数字相乘 O(|s|) 长数字。 optimal computational complexity of multiplication未知，但对于教科书乘法算法，这是 O(m |s|⁴) 总体。

(这个想法是计算每个由字符串尾部和数字 m′ ≤ m 组成的子问题的答案。有 O( m |s|) 这样的子问题和解决每个子问题涉及 O(|s|) 次 O(|s|) 数字长。)

在 Python 中，你可以这样编程，使用 @memoized decorator来自 Python 装饰器库:

@memoized
def max_product(s, m):
    """Return the maximum product of digits from the string s using m
    multiplication operators.

    """
    if m == 0:
        return int(s)
    return max(int(s[:i]) * max_product(s[i:], m - 1)
               for i in range(1, len(s) - m + 1))

如果您习惯于构建表的自下而上形式的动态规划，这种自上而下的形式可能看起来很奇怪，但实际上 @memoized decorator在函数的 cache 属性中维护表:

>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}