nums라는 숫자 목록이 있다고 가정하면 주어진 숫자 사이에 +, − 및 *와 같은 이항 연산자를 추가하여 생성할 수 있는 최대값도 찾아야 합니다. 유효한 대괄호를 삽입하십시오.
따라서 입력이 nums =[−6, −4, −10]과 같으면 출력은 100이 됩니다. 식을 ((−6) + (−4)) * −10과 같이 만들 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
OPS :=연산자 목록 [+, −, *]
-
N :=A의 크기
-
A의 모든 요소가 0이면
-
0 반환
-
-
dp() 함수를 정의합니다. 이것은 i, j가 걸릴 것입니다
-
i가 j와 같으면
-
쌍을 반환 (A[i], A[i])
-
-
낮음 :=inf, 높음 :=-inf
-
i ~ j − 1 범위의 k에 대해 수행
-
dp(i, k)의 각 왼쪽에 대해 수행
-
dp(k + 1, j)의 각 오른쪽에 대해 수행
-
OPS의 각 운영자 작업에 대해 수행
-
res :=왼쪽 op 오른쪽
-
res <낮으면
-
낮음 :=해상도
-
-
res> high이면
-
높음 :=해상도
-
-
-
-
-
-
리턴 쌍(낮음, 높음)
-
주요 방법에서 다음을 수행하십시오 -
-
답변 :=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