โปรแกรมหาค่าสูงสุดโดยแทรกตัวดำเนินการระหว่างตัวเลขในPython

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาค่าสูงสุดที่สามารถสร้างได้โดยการเพิ่มตัวดำเนินการไบนารีใดๆ เช่น +, − และ * ระหว่างตัวเลขที่กำหนดด้วย เช่นใส่วงเล็บที่ถูกต้อง

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[−6, −4, -10] ผลลัพธ์จะเป็น 100 เนื่องจากเราสามารถสร้างนิพจน์ได้ เช่น ((−6) + (−4)) * −10

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• OPS :=รายการตัวดำเนินการ [+, −, *]

• N :=ขนาด A

• ถ้าองค์ประกอบทั้งหมดใน A เป็น 0 แล้ว

  • คืนค่า 0

• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j

• ถ้าฉันเหมือนกับ j แล้ว

  • ส่งคืนคู่ (A[i], A[i])

• ต่ำ :=inf, สูง :=−inf

• สำหรับ k ในช่วง i ถึง j − 1 ทำ

  • สำหรับแต่ละที่เหลือใน dp(i, k) ทำ

    • สำหรับแต่ละสิทธิ์ใน dp(k + 1, j) ทำ

      • สำหรับโอเปอเรเตอร์แต่ละตัวใน OPS ให้ทำ

        • res :=ซ้าย op ขวา

        • ถ้า res <ต่ำ แล้ว

          • ต่ำ :=res

        • ถ้า res> สูง ก็

          • สูง :=ความละเอียด

• คู่กลับ (ต่ำ สูง)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ตอบ :=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