Chương trình tìm giá trị lớn nhất bằng cách chèn toán tử giữa các số trong Python

Cho danh sách số nums. Chèn phép toán +, -, * và ngoặc đơn tùy ý giữa các số để tạo biểu thức giá trị lớn nhất.

Ví dụ: [-6, -4, -10] → 100 (biểu thức ((-6) + (-4)) * (-10)).

Giải thuật (DP khoảng - Min/Max cho mỗi đoạn)

DP[i][j] = (min_val, max_val) của biểu thức từ i đến j.

• Cơ sở: i == j → (A[i], A[i]).
• Chia tại k (i ≤ k < j): kết hợp mọi left ∈ DP[i][k], right ∈ DP[k+1][j] với 3 phép toán.
• Cập nhật min/max cho đoạn [i,j].

Độ phức tạp O(n^3) do 3 vòng lặp lồng.

Ví dụ minh họa

import operator

class Solution:
    def solve(self, A):
        OPS = [operator.add, operator.sub, operator.mul]
        N = len(A)
        if not any(A):
            return 0
        
        from functools import lru_cache
        
        @lru_cache(None)
        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)
                            low = min(low, res)
                            high = max(high, res)
            return (low, high)
        
        return dp(0, N - 1)[1]

ob = Solution()
nums = [-6, -4, -10]
print(ob.solve(nums))  # Output: 100

Đầu vào / Đầu ra

Input: [-6, -4, -10]

Output: 100