পাইথনে জাম্প গেমে আমরা সর্বোচ্চ স্কোর পেতে পারি এমন প্রোগ্রাম

ধরুন আমাদের nums নামে একটি অ্যারে আছে এবং আরেকটি মান k। আমরা সূচক 0-এ আছি। এক চালে, আমরা অ্যারের সীমানার বাইরে না গিয়েই বেশিরভাগ k ধাপে লাফ দিতে পারি। আমরা অ্যারের চূড়ান্ত সূচকে পৌঁছাতে চাই। জাম্পিংয়ের জন্য আমরা স্কোর পাই, এটি অ্যারেতে দেখা প্রতিটি সূচক j-এর জন্য সমস্ত সংখ্যার যোগফল। আমরা পেতে পারি সর্বোচ্চ স্কোর খুঁজে বের করতে হবে.

সুতরাং, ইনপুট যদি nums =[1,-2,-5,7,-6,4] k =2 এর মত হয়, তাহলে আউটপুট হবে 10 কারণ, আমরা এই ক্রমটিতে লাফিয়ে পড়ি [1, -2, 7, 4], তাহলে আমরা সর্বোচ্চ পয়েন্ট পাব, এবং সেটা হল 10।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=সংখ্যার আকার
স্কোর :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূর্ণ
স্কোর[0] :=সংখ্যা[0]
currMax :=স্কোর[0]
max_pt :=0
যদি n <1 হয়, তাহলে
- রিটার্ন 0
যদি 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
    - idx-k থেকে idx রেঞ্জে p এর জন্য, করুন
      - যদি স্কোর[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