这是一个我面试时遇到的问题，我非常尴尬地被难住了。想知道是否有人能够想出答案并提供其大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|²）次将O（|s|）位数的数字相乘。目前尚不知道乘法的最优计算复杂度，但使用学校乘法算法，总复杂度为O（m |s|⁴）。
（想法是计算每个子问题的答案，该子问题由字符串的尾部和数字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}
s上花费线性时间。（原则上可以避免这种情况，但代码就不会那么优雅了 :) - Fred Foo@memoized 可以自动进行记忆化（即你的 A[position][count]），因此你不需要在 Python 代码中包含它。但是，在您的 Java 代码中需要这样做。 - justhalf我发现上面的DP解决方案很有帮助，但也很令人困惑。递归有些说得通，但我想在一个表格中完成所有操作而不需要最后检查。我花了很长时间来调试所有的索引，所以我保留了一些解释。
总结一下：
复杂度为O（N2k），因为最大化a的复杂度为O（N），我们对每个数字执行O（k）次。
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];
}
}
尽管Python已经展示了其功能优势并且击败了我，但是这里需要的是Java版本：
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))
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
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')
product_count 是部分答案中 * 出现次数的计数。因此，prev_product_count 是上一代的计数（范围从 0 到 n-1），而 product_count 是这一代的计数。至于 product，它是从调用 collections.namedtuple 中定义的。关于伪代码和真实代码，自下而上的解决方案自然有许多细节。如果您采用模糊的答案并尝试实现它，您会一遍又一遍地得到混乱的错误答案。 - btillypackage 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));
}
}
}
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");
}
}
我想到了一种方法，它是受到 bars and stars问题影响的暴力解决方案。
假设我们的数字是“12345”，我们需要使用2个*运算符。 我们可以将字符串12345看作
1_2_3_4_5
我们可以在任何下划线上放置两个星号操作符。由于有4个下划线和2个星号操作符，因此有4选2（或6）种不同的放置方式。比较这6种可能性并获取最大的数字。对于更大的字符串和更多的星号操作符，可以使用类似的方法。
我相信答案就是将*放在最大的数字前面，这样最大的数字会产生最大的影响。例如，如果我们有
1826456903521651
我们有五个乘法，这将是答案。
1*82*645*6*903521*651
所以运行时间将是线性的。
编辑：好的，这是错误的。我们有两个反例。
198 中放置一个 *。 - Fred Foo
31!^2非常大... - Ben