数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：在数字之间插入运算符以查找最大值
假设我们有一组数字，称为nums，我们需要找到通过在给定数字之间添加任何二元运算符（例如+，-和*）以及插入任何有效括号可以生成的 最大值。
因此，如果输入类似于nums = [-6，-4，-10]，则输出将为100，因为我们可以创建类似于：((-6) + (-4)) * -10 的表达式。
为了解决这个问题，我们将遵循以下步骤：
OPS := 运算符列表 [+, -, *]
N := A 的大小
如果A中的所有元素都是0，则
返回 0
定义一个函数 dp()。这将采用 i, j
如果 i 等于 j，则
返回一个 (A[i], A[i]) 对
low := inf, high := -inf
对于 k 的范围从 i 到 j - 1，执行以下操作：
对于 dp(i, k) 中的每个 left，执行以下操作：
对于 dp(k + 1, j) 中的每个 right，执行以下操作：
对于 OPS 中的每个运算符 op，执行以下操作：
res := left op right
如果 res < low，则
low := res
如果 res > high，则
high := res
返回 (low, high) 对
从主方法执行以下操作：
ans := dp(0, N - 1)
返回 ans 的第二个值
让我们看一下下面的实现，以便更好地理解：
示例
import operator
class Solution:
def solve(self, A):
OPS = [operator.add, operator.sub, operator.mul]
N = len(A)
if not any(A):
return 0
def dp(i, j):
if i == j:
return [A[i], A[i]]
low = float("inf")
high = float("−inf")
for k in range(i, j):
for left in dp(i, k):
for right in dp(k + 1, j):
for op in OPS:
res = op(left, right)
if res < low:
low = res
if res > high:
high = res
return [low, high]
return dp(0, N − 1)[1]
ob = Solution()
nums = [−6, −4, −10]
print(ob.solve(nums))输入
[−6, −4, −10]
输出
100
更新于：2020年12月15日
264 次浏览
广告