পাইথনে একটি ভাল সাবয়ারের সর্বাধিক স্কোর খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের nums নামে একটি অ্যারে আছে এবং একটি মান k আছে। একটি subarray এর স্কোর বিবেচনা করুন (i, j) ন্যূনতম subarray nums [i..j] * (j-i+1) হিসাবে সংজ্ঞায়িত করা হয়। এখন, একটি ভাল সাবয়ারে একটি সাবয়ারে যেখানে i <=k <=j। আমাদের একটি ভাল সাবয়ারের সর্বোচ্চ সম্ভাব্য স্কোর খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি nums =[2,5,4,8,5,6] k =3 এর মত হয়, তাহলে আউটপুট হবে 20 কারণ সর্বোত্তম সাবয়ারে এখানে (1, 5), তাই ন্যূনতম সংখ্যা[1] ..5] হল 4, তাই 4*(5-1+1) =20

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

উত্তর :=সংখ্যা[k], minNum :=nums[k]
i :=k, j :=k
যখন i> -1 বা j <সংখ্যার আকার, কর
- যখন i> -1 এবং nums[i]>=minNum, do
  - i :=i - 1
- যখন j <সংখ্যা এবং সংখ্যার আকার [j]>=minNum, করুন
  - j :=j + 1
- ans :=সর্বাধিক উত্তর এবং ((j - i - 1) * minNum)
- minNum :=সর্বাধিক (সংখ্যা[i] যদি i> -1 অন্যথায় -1) এবং (সংখ্যা[j] যদি j <সংখ্যার আকার অন্যথায় -1)
উত্তর ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(nums, k):
   ans = nums[k]
   minNum = nums[k]
   i = k
   j = k
   while i > -1 or j < len(nums):
      while i > -1 and nums[i] >= minNum:
         i -= 1
      while j < len(nums) and nums[j] >= minNum:
         j += 1
      ans = max(ans, (j - i - 1) * minNum)
      minNum = max(nums[i] if i > -1 else -1 , nums[j] if j <
len(nums) else -1)
   return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))

ইনপুট

[2,5,4,8,5,6], 3