ধরুন আমাদের একটি অ্যারে সংখ্যা আছে, একটি র্যাম্প হল একটি টিপল (i, j) যার জন্য i
সুতরাং, যদি ইনপুটটি nums =[6,0,8,2,1,5] এর মত হয়, তাহলে আউটপুট হবে 4 কারণ সর্বাধিক প্রস্থের র্যাম্প (i, j) =(1, 5) এবং সংখ্যায় অর্জিত হয়। [1] =0 এবং সংখ্যা[5] =5।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
B :=একটি নতুন মানচিত্র
-
আমি 0 থেকে সংখ্যার আকারের মধ্যে, কর
-
x :=সংখ্যা[i]
-
যদি x B তে থাকে, তাহলে
-
B[x]
-এর শেষে i ঢোকান
-
-
অন্যথায়,
-
B[x] :=[i]
-
-
-
mini :=একটি তালিকা প্রাথমিকভাবে এটিতে একটি তথ্য সংরক্ষণ করে
-
maxi :=একটি তালিকা প্রাথমিকভাবে এটিতে একটি -inf সঞ্চয় করে
-
প্রতিটি x-এর জন্য B-এর সমস্ত কীগুলির তালিকার তালিকা সাজান, করুন
-
মিনির শেষ উপাদানের ন্যূনতম এবং মিনির শেষে ন্যূনতম B[x] সন্নিবেশ করান
-
-
B-এর সমস্ত কীগুলির বিপরীতভাবে সাজানো তালিকায় প্রতিটি x-এর জন্য, করুন
-
মিনির শেষ উপাদানের ন্যূনতম এবং মিনির শেষে ন্যূনতম B[x] সন্নিবেশ করান
-
-
maxi :=রিভার্স ম্যাক্সি তারপর শুরু থেকে দ্বিতীয় শেষ উপাদানে সাবয়ারে নিন
-
মিনি :=মিনির সাবয়ারে[সূচী 1 থেকে শেষ পর্যন্ত]
-
p :=0
-
res :=-inf
-
যখন p <মিনির আকার, করুন
-
res :=res এর সর্বোচ্চ এবং (maxi[p] - mini[p])
-
p :=p + 1
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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]
আউটপুট
4