c++ - 查找产品的最大值以及数组中元素的加减法和除法

Question

您好，我有以下问题需要解决:

我有两个数组n整数数组和n - 1操作数组

• integers[n]//n 个整数
• operations[n - 1]//n - 1 操作(例如 + - */)

数字数组是固定的，而运算符数组可以用于任意排列以获得最大值(谢谢@ grek40 )

示例 1:

给定整数数组:1 2 7 5 1 2 和操作数组:+++ + *

我想找到最大的相邻乘积和减法，即 1+2+7*5+1+2 = 41

示例 2:

给定整数数组:1 3 5 6 9 10 12 14 和操作数组:+ + * * -//

我想找到最大的相邻乘积和减法，即 1-3/5/6+9+10*12*14 = 1689.9

我是动态规划的初学者。我无法找出以下问题的递归关系。

谁能给我点建议？

谢谢!

我尝试使用枚举方法，时间复杂度是n!

for operators in allOperators:
    op = list(operators)
    op.append(' ')
    operation = ""

    for i, number in enumerate(inputNumbers):
        count += 1
        operation += number + op[i]
    output = eval(operation)

    if output > maxOutput:
        maxOutput = output

Answer 1

对于这个问题，代码比文字更好。代码中状态转移方程很清楚。

import functools
test1 = (1, 2, 7, 5, 1, 2)
test2 = (1, 3, 5, 6 ,9 ,10, 12, 14)
@functools.lru_cache()
def BaseSolution(nums, add, sub, mul, div, length):
    if  add<0 or sub<0 or mul<0 or div<0 or length<0:
         return float("-inf")
    if  length == 0:
        return nums[length]
    else:
        return max(
            BaseSolution(nums, add-1, sub, mul, div, length-1) + nums[length],
            BaseSolution(nums, add, sub-1, mul, div, length-1) - nums[length],
            MulOrDivSolution(nums, add, sub, mul-1, div, length-1, '*'+str(nums[length])),
            MulOrDivSolution(nums, add, sub, mul, div-1, length-1, '/'+str(nums[length])),
            )
def MulOrDivSolution(nums, add, sub, mul, div, length, lzayVal):
    if  add<0 or sub<0 or mul<0 or div<0 or length<0:
         return float("-inf")
    if  length == 0:
        return eval( str(nums[length])+lzayVal)
    else:   
        return max(
            BaseSolution(nums, add-1, sub, mul, div, length-1) + eval( str(nums[length])+lzayVal),
            BaseSolution(nums, add, sub-1, mul, div, length-1) - eval( str(nums[length])+lzayVal),
            MulOrDivSolution(nums, add, sub, mul-1, div, length-1, '*'+str(nums[length])+lzayVal),
            MulOrDivSolution(nums, add, sub, mul, div-1, length-1, '/'+str(nums[length])+lzayVal),
            )
if __name__ == '__main__':
    print(BaseSolution(test1,4,0,0,1,5))
    print(BaseSolution(test2,2,1,2,2,7))