这是我遇到的一个面试问题，我很尴尬地被它难住了。想知道是否有人可以想出答案并为其提供大 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。后者显然是正确的答案。
我在这里假设所需的乘法运算符数量m是问题的一部分，以及数字字符串s。
您可以使用表格方法（又称“动态规划”）解决此问题，其中 O( m | s | 2 ) 乘以 O(| s |) 位长的数字。乘法的最佳计算复杂度是未知的，但对于教科书乘法算法，这总体上是 O( m | s | 4 )。
（这个想法是计算每个子问题的答案，每个子问题由字符串的尾部和数字m ' ≤ m组成。有 O( m | s |) 这样的子问题，解决每个子问题都涉及 O(| s |) 的乘法长度为 O(| s |) 位的数字。）
在 Python 中，您可以像这样使用Python 装饰器库中的@memoized装饰器对其进行编程：
@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装饰器cache在函数的属性中维护了表：
>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}
我发现上述 DP 解决方案很有帮助但令人困惑。重复出现是有道理的，但我想在没有最后检查的情况下在一张表中完成所有操作。我花了很长时间调试所有索引，所以我保留了一些解释。
回顾一下：
复杂性是 O(N 2 k)，因为在 a 上最大化是 O(N)，我们对每个数字执行 O(k) 次 (O(N))。
public class MaxProduct {
public static void main(String ... args) {
System.out.println(solve(args[0], Integer.parseInt(args[1])));
}
static long solve(String digits, int k) {
if (k == 0)
return Long.parseLong(digits);
int N = digits.length();
long[][] T = new long[N][k+1];
for (int i = 0; i < N; i++) {
T[i][0] = Long.parseLong(digits.substring(0,i+1));
for (int j = 1; j <= Math.min(k,i); j++) {
long max = Integer.MIN_VALUE;
for (int a = 0; a < i; a++) {
long l = Long.parseLong(digits.substring(a+1,i+1));
long prod = l * T[a][j-1];
max = Math.max(max, prod);
}
T[i][j] = max;
}
}
return T[N-1][k];
}
}
java 版本，虽然 Python 已经展示了它的功能优势并击败了我：
private static class Solution {
BigInteger product;
String expression;
}
private static Solution solve(String digits, int multiplications) {
if (digits.length() < multiplications + 1) {
return null; // No solutions
}
if (multiplications == 0) {
Solution solution = new Solution();
solution.product = new BigInteger(digits);
solution.expression = digits;
return solution;
}
// Position of first '*':
Solution max = null;
for (int i = 1; i < digits.length() - (multiplications - 1); ++i) {
BigInteger n = new BigInteger(digits.substring(0, i));
Solution solutionRest = solve(digits.substring(i), multiplications - 1);
n = n.multiply(solutionRest.product);
if (max == null || n.compareTo(max.product) > 0) {
solutionRest.product = n;
solutionRest.expression = digits.substring(0, i) + "*"
+ solutionRest.expression;
max = solutionRest;
}
}
return max;
}
private static void test(String digits, int multiplications) {
Solution solution = solve(digits, multiplications);
System.out.printf("%s %d -> %s = %s%n", digits, multiplications,
solution.expression, solution.product.toString());
}
public static void main(String[] args) {
test("1826456903521651", 5);
}
输出
1826456903521651 5 -> 182*645*6*903*521*651 = 215719207032420
这是一个迭代动态编程解决方案。
与递归版本相反（应该有类似的运行时间）。
基本思想：
A[position][count]是可以position使用count乘法获得的在位置结束的最大数。
所以：
A[position][count] = max(for i = 0 to position
A[i][count-1] * input.substring(i, position))
对每个位置和每个计数执行此操作，然后以所需的乘法次数将每个位置与整个剩余字符串相乘。
复杂：
给定一个要插入乘法运算符的字符串|s|...m
O(m|s|2g(s))g(s)乘法的复杂度在哪里。
Java代码：
static long solve(String digits, int multiplications)
{
if (multiplications == 0)
return Long.parseLong(digits);
// Preprocessing - set up substring values
long[][] substrings = new long[digits.length()][digits.length()+1];
for (int i = 0; i < digits.length(); i++)
for (int j = i+1; j <= digits.length(); j++)
substrings[i][j] = Long.parseLong(digits.substring(i, j));
// Calculate multiplications from the left
long[][] A = new long[digits.length()][multiplications+1];
A[0][0] = 1;
for (int i = 1; i < A.length; i++)
{
A[i][0] = substrings[0][i];
for (int j = 1; j < A[0].length; j++)
{
long max = -1;
for (int i2 = 0; i2 < i; i2++)
{
long l = substrings[i2][i];
long prod = l * A[i2][j-1];
max = Math.max(max, prod);
}
A[i][j] = max;
}
}
// Multiply left with right and find maximum
long max = -1;
for (int i = 1; i < A.length; i++)
{
max = Math.max(max, substrings[i][A.length] * A[i][multiplications]);
}
return max;
}
一个非常基本的测试：
System.out.println(solve("99287", 1));
System.out.println(solve("99287", 2));
System.out.println(solve("312", 1));
印刷：
86304
72036
62
是的，它只打印最大值。如果需要，让它实际打印总和并不难。
这是另一个 Java 解决方案。（我知道“312”和 1 乘法是正确的，我认为它适用于其他人......
您必须记住如何自己获得递归方法的复杂性，哈哈。
package test;
import java.util.ArrayList;
import java.util.List;
public class BiggestNumberMultiply {
private static class NumberSplit{
String[] numbers;
long result;
NumberSplit(String[] numbers){
this.numbers=numbers.clone();
result=1;
for(String n:numbers){
result*=Integer.parseInt(n);
}
}
@Override
public String toString() {
StringBuffer sb=new StringBuffer();
for(String n:numbers){
sb.append(n).append("*");
}
sb.replace(sb.length()-1, sb.length(), "=")
.append(result);
return sb.toString();
}
}
public static void main(String[] args) {
String numbers = "312";
int numMults=1;
int numSplits=numMults;
List<NumberSplit> splits = new ArrayList<NumberSplit>();
splitNumbersRecursive(splits, new String[numSplits+1], numbers, numSplits);
NumberSplit maxSplit = splits.get(0);
for(NumberSplit ns:splits){
System.out.println(ns);
if(ns.result>maxSplit.result){
maxSplit = ns;
}
}
System.out.println("The maximum is "+maxSplit);
}
private static void splitNumbersRecursive(List<NumberSplit> list, String[] splits, String numbers, int numSplits){
if(numSplits==0){
splits[splits.length-1] = numbers;
return;
}
for(int i=1; i<=numbers.length()-numSplits; i++){
splits[splits.length-numSplits-1] = numbers.substring(0,i);
splitNumbersRecursive(list, splits, numbers.substring(i), numSplits-1);
list.add(new NumberSplit(splits));
}
}
}
又一个 Java 实现。这是自上而下的 DP，也就是 memoization。除了最大产品之外，它还打印出实际组件。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MaxProduct {
private static Map<Key, Result> cache = new HashMap<>();
private static class Key {
int operators;
int offset;
Key(int operators, int offset) {
this.operators = operators;
this.offset = offset;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + offset;
result = prime * result + operators;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof Key)) {
return false;
}
Key other = (Key) obj;
if (offset != other.offset) {
return false;
}
if (operators != other.operators) {
return false;
}
return true;
}
}
private static class Result {
long product;
int offset;
Result prev;
Result (long product, int offset) {
this.product = product;
this.offset = offset;
}
@Override
public String toString() {
return "product: " + product + ", offset: " + offset;
}
}
private static void print(Result result, String input, int operators) {
System.out.println(operators + " multiplications on: " + input);
Result current = result;
System.out.print("Max product: " + result.product + " = ");
List<Integer> insertions = new ArrayList<>();
while (current.prev != null) {
insertions.add(current.offset);
current = current.prev;
}
List<Character> inputAsList = new ArrayList<>();
for (char c : input.toCharArray()) {
inputAsList.add(c);
}
int shiftedIndex = 0;
for (int insertion : insertions) {
inputAsList.add(insertion + (shiftedIndex++), '*');
}
StringBuilder sb = new StringBuilder();
for (char c : inputAsList) {
sb.append(c);
}
System.out.println(sb.toString());
System.out.println("-----------");
}
public static void solve(int operators, String input) {
cache.clear();
Result result = maxProduct(operators, 0, input);
print(result, input, operators);
}
private static Result maxProduct(int operators, int offset, String input) {
String rightSubstring = input.substring(offset);
if (operators == 0 && rightSubstring.length() > 0) return new Result(Long.parseLong(rightSubstring), offset);
if (operators == 0 && rightSubstring.length() == 0) return new Result(1, input.length() - 1);
long possibleSlotsForFirstOperator = rightSubstring.length() - operators;
if (possibleSlotsForFirstOperator < 1) throw new IllegalArgumentException("too many operators");
Result maxProduct = new Result(-1, -1);
for (int slot = 1; slot <= possibleSlotsForFirstOperator; slot++) {
long leftOperand = Long.parseLong(rightSubstring.substring(0, slot));
Result rightOperand;
Key key = new Key(operators - 1, offset + slot);
if (cache.containsKey(key)) {
rightOperand = cache.get(key);
} else {
rightOperand = maxProduct(operators - 1, offset + slot, input);
}
long newProduct = leftOperand * rightOperand.product;
if (newProduct > maxProduct.product) {
maxProduct.product = newProduct;
maxProduct.offset = offset + slot;
maxProduct.prev = rightOperand;
}
}
cache.put(new Key(operators, offset), maxProduct);
return maxProduct;
}
public static void main(String[] args) {
solve(5, "1826456903521651");
solve(1, "56789");
solve(1, "99287");
solve(2, "99287");
solve(2, "312");
solve(1, "312");
}
}
奖励：任何有兴趣的人都可以使用暴力破解。不是特别聪明，但它使回溯步骤变得简单。
import java.util.ArrayList;
import java.util.List;
public class MaxProductBruteForce {
private static void recurse(boolean[] state, int pointer, int items, List<boolean[]> states) {
if (items == 0) {
states.add(state.clone());
return;
}
for (int index = pointer; index < state.length; index++) {
state[index] = true;
recurse(state, index + 1, items - 1, states);
state[index] = false;
}
}
private static List<boolean[]> bruteForceCombinations(int slots, int items) {
List<boolean[]> states = new ArrayList<>(); //essentially locations to insert a * operator
recurse(new boolean[slots], 0, items, states);
return states;
}
private static class Tuple {
long product;
List<Long> terms;
Tuple(long product, List<Long> terms) {
this.product = product;
this.terms = terms;
}
@Override
public String toString() {
return product + " = " + terms.toString();
}
}
private static void print(String input, int operators, Tuple result) {
System.out.println(operators + " multiplications on: " + input);
System.out.println(result.toString());
System.out.println("---------------");
}
public static void solve(int operators, String input) {
Tuple result = maxProduct(input, operators);
print(input, operators, result);
}
public static Tuple maxProduct(String input, int operators) {
Tuple maxProduct = new Tuple(-1, null);
for (boolean[] state : bruteForceCombinations(input.length() - 1, operators)) {
Tuple newProduct = getProduct(state, input);
if (maxProduct.product < newProduct.product) {
maxProduct = newProduct;
}
}
return maxProduct;
}
private static Tuple getProduct(boolean[] state, String input) {
List<Long> terms = new ArrayList<>();
List<Integer> insertLocations = new ArrayList<>();
for (int i = 0; i < state.length; i++) {
if (state[i]) insertLocations.add(i + 1);
}
int prevInsert = 0;
for (int insertLocation : insertLocations) {
terms.add(Long.parseLong(input.substring(prevInsert, insertLocation))); //gradually chop off the string
prevInsert = insertLocation;
}
terms.add(Long.parseLong(input.substring(prevInsert))); //remaining of string
long product = 1;
for (long term : terms) {
product = product * term;
}
return new Tuple(product, terms);
}
public static void main(String[] args) {
solve(5, "1826456903521651");
solve(1, "56789");
solve(1, "99287");
solve(2, "99287");
solve(2, "312");
solve(1, "312");
}
}
此实现适用于@lars。
from __future__ import (print_function)
import collections
import sys
try:
xrange
except NameError: # python3
xrange = range
def max_product(s, n):
"""Return the maximum product of digits from the string s using m
multiplication operators.
"""
# Guard condition.
if len(s) <= n:
return None
# A type for our partial solutions.
partial_solution = collections.namedtuple("product",
["value", "expression"])
# Initialize the best_answers dictionary with the leading terms
best_answers = {}
for i in xrange(len(s)):
term = s[0: i+1]
best_answers[i+1] = partial_solution(int(term), term)
# We then replace best_answers n times.
for prev_product_count in [x for x in xrange(n)]:
product_count = prev_product_count + 1
old_best_answers = best_answers
best_answers = {}
# For each position, find the best answer with the last * there.
for position in xrange(product_count+1, len(s)+1):
candidates = []
for old_position in xrange(product_count, position):
prior_product = old_best_answers[old_position]
term = s[old_position:position]
value = prior_product.value * int(term)
expression = prior_product.expression + "*" + term
candidates.append(partial_solution(value, expression))
# max will choose the biggest value, breaking ties by the expression
best_answers[position] = max(candidates)
# We want the answer with the next * going at the end of the string.
return best_answers[len(s)]
print(max_product(sys.argv[1], int(sys.argv[2])))
这是一个示例运行：
$ python mult.py 99287 2
product(value=72036, expression='9*92*87')
希望逻辑从实现中清楚。
我想到了，这是受酒吧和明星问题影响的蛮力方法。
假设我们的号码是“12345”，我们需要使用 2 个 * 运算符。我们可以将字符串 12345 视为
1_2_3_4_5
我们可以将两个 * 运算符放在任何下划线上。由于有 4 个下划线和 2 个 * 运算符，因此有 4 种选择 2（或 6）种不同的方式来放置运算符。比较这 6 种可能性并抓住最大的数字。类似的方法可用于更大的字符串和更多的 * 运算符。
我很确定答案是简单地将*s 放在最大的数字之前，这样最大的数字就会产生最大的影响。例如，如果我们有
1826456903521651
我们有五个乘法，这就是答案。
1*82*645*6*903521*651
所以运行时间是线性的。
编辑：好的，所以这是错误的。我们有两个反例。