ค้นหาจำนวนรวมสูงสุดของตัวเลขใน Python

สมมติว่าเรามีตัวเลขที่กำหนด N ซึ่งอยู่ในช่วง (1<=N<=10^9) เราต้องแทน N เป็นผลรวมของจำนวนรวมสูงสุดที่เป็นไปได้และ คืนค่าจำนวนที่มากที่สุดนี้ มิฉะนั้น เมื่อเราไม่พบการแยกใดๆ ให้คืนค่า -1

ดังนั้นหากอินพุตเท่ากับ 16 แล้วเอาต์พุตจะเป็น 4 เนื่องจาก 16 สามารถเขียนเป็น 4 + 4 + 4 + 4 หรือ 8 + 8 ได้ แต่ (4 + 4 + 4 + 4) มีผลรวมสูงสุด

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

• max_val :=16

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

• table :=รายการขนาด max_val แล้วเก็บ -1 ไว้ที่แต่ละตำแหน่ง

• ตาราง[0] :=0

• v :=[4, 6, 9]

• สำหรับฉันอยู่ในช่วง 1 ถึง max_val เพิ่มขึ้น 1 ทำ

  • สำหรับ k ในช่วง 0 ถึง 2 ทำ

    • j :=v[k]

    • ถ้า i>=j และ table[i - j] ไม่ใช่ -1 แล้ว

      • table[i] :=สูงสุดของ table[i], table[i - j] + 1

• กลับตาราง

• กำหนดฟังก์ชัน max_summ() นี่จะเป็นตาราง n

• ถ้า n

  • กลับตาราง[n]

• มิฉะนั้น

  • t :=จำนวนเต็มของ ((n - max_val) / 4) + 1

  • กลับ t + ตาราง[n - 4 * t]

• จากวิธีหลัก ให้ทำดังนี้ −

• ตาราง :=pre_calc()

• แสดง max_summ(ตาราง n)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))

อินพุต

16

ผลลัพธ์

4