สมมติว่า Amal และ Bimal กำลังเล่นเกม พวกเขามีหมายเลขอาร์เรย์ที่กำหนด n ก้อนอิฐที่มีหมายเลขอยู่ด้านบน ในเกมนี้ ผู้เล่นสามารถถอดอิฐหนึ่ง สอง หรือสามก้อนออกจากด้านบน และตัวเลขที่ทำเครื่องหมายบนก้อนอิฐที่ถูกถอดออกจะถูกเพิ่มเข้าไปในคะแนนของผู้เล่นนั้น ถ้า Amal เริ่มก่อนเสมอ เราต้องหาว่า Amal ได้คะแนนสูงสุดเท่าไหร่
ดังนั้น หากอินพุตเท่ากับ nums =[1,2,3,4,5] ผลลัพธ์จะเป็น 6 เพราะ Amal สามารถลบอิฐ {1}, {1,2} หรือ {1,2,3} หาก Amal เลือกสองหรือสามองค์ประกอบแรก Bimal สามารถรับทั้งหมดและรับคะแนนสูงสุด แต่ถ้า Amal เลือก 1 ในตอนแรก Bimal สามารถรับได้มากที่สุด {2,3,4} =9 และ Amal สามารถรับ 5 ได้ดังนั้นทั้งหมด คะแนน Amal คือ 1+5 =6.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
- INF :=9999
- n :=ขนาดของ nums
- ย้อนกลับหมายเลขรายการ
- temp :=อาร์เรย์ขนาด n และเติม 0
- ผลรวม :=อาร์เรย์ขนาด n และเติม 0
- สำหรับแต่ละดัชนี i และค่า val เป็น nums ทำ
- total[i] :=total[i-1] + val
- อุณหภูมิ[0] :=nums[0]
- อุณหภูมิ[1] :=temp[0]+nums[1]
- อุณหภูมิ[2] :=temp[1]+nums[2]
- สำหรับฉันในช่วง 3 ถึง n - 1 ทำ
- a :=nums[i]
- b :=nums[i] + nums[i-1]
- c :=nums[i] + nums[i-1] + nums[i-2]
- อุณหภูมิ[i] :=สูงสุดของ a, b, c
- อุณหภูมิกลับ[n-1]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
INF = 99999 def solve(nums): n = len(nums) nums.reverse() temp = [0]*n total = [0]*n for i, val in enumerate(nums): total[i] = total[i-1] + val temp[0] = nums[0] temp[1] = temp[0]+nums[1] temp[2] = temp[1]+nums[2] for i in range(3, n): a = nums[i] b = nums[i] + nums[i-1] c = nums[i] + nums[i-1] + nums[i-2] temp[i] = max(a, b, c) return temp[n-1] nums = [1,2,3,4,5] print(solve(nums))
อินพุต
[1,2,3,4,5]
ผลลัพธ์
6
