পাইথনে সর্বোচ্চ প্রস্থের র্যাম্প বের করার প্রোগ্রাম

মনে করুন nums নামক একটি অ্যারে আছে। একটি র্যাম্প হলো একটি টাপল (i, j) যেখানে i < j এবং nums[i] <= nums[j]। এমন একটি র্যাম্পের প্রস্থ হলো (j-i)। আমাদের nums-এ সর্বোচ্চ প্রস্থের র্যাম্প বের করতে হবে। যদি এমন কোনো র্যাম্প না থাকে, তবে ০ রিটার্ন করুন।

যেমন, ইনপুট nums = [6,0,8,2,1,5] হলে, আউটপুট হবে ৪ কারণ সর্বোচ্চ প্রস্থের র্যাম্প (i, j) = (1, 5)-এ পাওয়া যায় এবং nums[1] = 0, nums[5] = 5।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

B := একটি নতুন ম্যাপ
i = 0 থেকে nums-এর সাইজ - ১ পর্যন্ত
- x := nums[i]
- যদি x B-এ থাকে, তবে
  - i কে B[x]-এর শেষে অ্যাপেন্ড করুন
- অন্যথায়,
  - B[x] := [i]
mini := [inf] দিয়ে ইনিশিয়ালাইজড একটি লিস্ট
maxi := [-inf] দিয়ে ইনিশিয়ালাইজড একটি লিস্ট
B-এর সব কী সর্টেড লিস্ট-এ জন্য
- mini-এর শেষ এলিমেন্ট এবং B[x]-এর মিনিমামের মিনিমাম কে mini-এ অ্যাপেন্ড করুন
B-এর সব কী রিভার্স সর্টেড লিস্ট-এ জন্য
- maxi-এর শেষ এলিমেন্ট এবং B[x]-এর ম্যাক্সিমামের ম্যাক্সিমাম কে maxi-এ অ্যাপেন্ড করুন
maxi := রিভার্স করা maxi এর শুরু থেকে দ্বিতীয় শেষ এলিমেন্ট পর্যন্ত
mini := mini[1:] (দ্বিতীয় এলিমেন্ট থেকে শেষ)
p := 0, res := -inf
যখন p < mini-এর সাইজ, तब
- res := max(res, maxi[p] - mini[p])
- p := p + 1
res রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

def solve(nums):    B = {}    for i in range(len(nums)):       x = nums[i]       if x in B:          B[x].append(i)       else:          B[x] = [i]    mini = [float('inf')]    maxi = [float('-inf')]    for x in sorted(B.keys()):       mini.append(min(mini[-1], min(B[x])))    for x in sorted(B.keys(), reverse = True):       maxi.append(max(maxi[-1], max(B[x])))    maxi = maxi[::-1][:-1]    mini = mini[1:]    p = 0    res = float('-inf')    while p < len(mini):       res = max(res, maxi[p] - mini[p])       p += 1 return res nums = [6,0,8,2,1,5] print(solve(nums))

ইনপুট

[6,0,8,2,1,5]