โปรแกรมหาคะแนนสูงสุดที่เราจะได้ในเกมกระโดดใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราอยู่ที่ดัชนี 0 ในการย้ายครั้งเดียว เราสามารถกระโดดได้ไม่เกิน k ขั้นโดยไม่ต้องออกนอกขอบเขตของอาร์เรย์ เราต้องการเข้าถึงดัชนีสุดท้ายของอาร์เรย์ สำหรับการกระโดด เราได้คะแนน นั่นคือผลรวมของ nums[j] ทั้งหมดสำหรับแต่ละดัชนี j ที่เราเข้าชมในอาร์เรย์ เราต้องหาคะแนนสูงสุดให้ได้

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1,-2,-5,7,-6,4] k =2 ผลลัพธ์จะเป็น 10 เพราะเรากระโดดในลำดับนี้ [1, -2, 7, 4] แล้วเราจะได้คะแนนสูงสุด นั่นคือ 10

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

• n :=ขนาดของ nums
• คะแนน :=อาร์เรย์ขนาด n และเติมด้วย 0
• คะแนน[0] :=nums[0]
• currMax :=คะแนน[0]
• max_pt :=0
• ถ้า n <1 แล้ว
  • คืน 0
• ถ้า n เหมือนกับ 1 แล้ว
  • คืนค่าองค์ประกอบสุดท้ายของ nums
• สำหรับ idx ในช่วง 1 ถึง n - 1 ทำ
  • ถ้า max_pt>=idx - k แล้ว
    • ถ้า currMax <คะแนน[idx-1] และ idx> 0 แล้ว
      • currMax :=คะแนน[idx-1]
      • max_pt :=idx-1
  • มิฉะนั้น
    • ถ้า idx - k> 0 แล้ว
      • currMax :=คะแนน[idx-k]
      • max_pt :=idx - k
      • สำหรับ p ในช่วง idx-k ถึง idx ทำ
        • ถ้าคะแนน[p]>=currMax แล้ว
          • max_pt :=p
          • currMax :=คะแนน[p]
  • คะแนน[idx] :=currMax + nums[idx]
• องค์ประกอบสุดท้ายของคะแนน :=currMax + nums[-1]
• คืนค่าองค์ประกอบสุดท้ายของคะแนน

ตัวอย่าง

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

def solve(nums, k):
   n = len(nums)
   scores = [0] * n
   scores[0] = nums[0]
   currMax = scores[0]
   max_pt = 0

   if n < 1:
      return 0
   if n == 1:
      return nums[-1]

   for idx in range(1,n):
      if max_pt >= idx - k:
         if currMax < scores[idx-1] and idx > 0:
            currMax = scores[idx-1]
            max_pt = idx-1
      else:
         if idx - k > 0:
            currMax = scores[idx-k]
            max_pt = idx - k
            for p in range(idx-k, idx):
               if scores[p] >= currMax:
                  max_pt = p
                  currMax = scores[p]
      scores[idx] = currMax + nums[idx]
   scores[-1] = currMax + nums[-1]
   return scores[-1]

nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))

อินพุต

[1,-2,-5,7,-6,4], 2

ผลลัพธ์

10