資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告