โปรแกรมหาค่าสูงสุดจากการแทรกตัวดำเนินการ + - * ในลิสต์ตัวเลข Python

ได้รับลิสต์ตัวเลข nums แทรก +, -, * และวงเล็บได้อย่างใดๆ หา ค่าสูงสุดที่เป็นไปได้

ตัวอย่าง

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

Output: 100

นิพจน์: ((-6) + (-4)) * (-10) = (-10) * (-10) = 100

แนวทางแก้ปัญหา

Interval DP (Matrix Chain Multiplication style):

• dp(i, j) = (min_val, max_val) ของนิพจน์จาก nums[i..j]
• Base: i == j → (nums[i], nums[i])
• Split at k: ลองทุก k และทุก operator คำนวณ min/max จาก left/right

การใช้งาน (Python)

import operator
from functools import lru_cache

class Solution:
    def solve(self, A):
        OPS = [operator.add, operator.sub, operator.mul]
        n = len(A)
        
        if not any(A):
            return 0
        
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return (A[i], A[i])
            
            lo, hi = float('inf'), float('-inf')
            
            for k in range(i, j):
                left_min, left_max = dp(i, k)
                right_min, right_max = dp(k + 1, j)
                
                for op in OPS:
                    # ลองทุก combination ของ min/max
                    for a in (left_min, left_max):
                        for b in (right_min, right_max):
                            res = op(a, b)
                            lo = min(lo, res)
                            hi = max(hi, res)
            
            return (lo, hi)
        
        return dp(0, n - 1)[1]

# ทดสอบ
ob = Solution()
print(ob.solve([-6, -4, -10]))  # Output: 100

ความซับซ้อน

• Time Complexity: O(N³ × 3 × 4) = O(N³)
• Space Complexity: O(N²)

หมายเหตุ: รุ่นต้นฉบับคืน list [low, high] ซึ่งทำงานได้แต่ tuple เร็วกว่าและ hashable สำหรับ lru_cache