पायथन में संख्याओं के बीच ऑपरेटर डालकर अधिकतम मान ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हमें दिए गए संख्याओं के बीच +, -, * जैसे किसी भी बाइनरी ऑपरेटर को जोड़कर और वैध कोष्ठक डालकर उत्पन्न किए जा सकने वाले अधिकतम मान को ज्ञात करना है।

उदाहरण के लिए, nums = [-6, -4, -10] के लिए आउटपुट 100 होगा (अभिव्यक्ति: ((-6) + (-4)) * -10)।

एल्गोरिदम (इंटरवल DP)

• OPS := [+, -, *]
• N := len(A)
• यदि सभी तत्व 0 हैं, तो 0 वापस करें
• dp(i, j) फ़ंक्शन परिभाषित करें जो (min_val, max_val) वापस करता है:
  • यदि i == j, तो (A[i], A[i]) वापस करें
  • low := inf, high := -inf
  • k = i से j-1 तक:
    • प्रत्येक left in dp(i,k) और right in dp(k+1,j) के लिए:
      • प्रत्येक op in OPS के लिए:
        • res = left op right
        • low = min(low, res), high = max(high, res)
  • (low, high) वापस करें
• dp(0, N-1)[1] वापस करें

उदाहरण

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