ধরুন আমাদের কাছে একটি 2D সমতলে স্থানাঙ্ক বিন্দু সমন্বিত পয়েন্ট নামক একটি অ্যারে আছে, সেগুলিকে x-মান দ্বারা সাজানো হয়েছে, যেখানে পয়েন্ট[i] =(x_i, y_i) তাই x_i
সুতরাং, ইনপুট যদি পয়েন্টের মত হয় =[[2,4],[3,1],[6,11],[7,-9]] k =1, তাহলে আউটপুট হবে 6 কারণ প্রথম দুটি পয়েন্ট শর্ত পূরণ করুন |xi - xj| <=1 এখন যদি আমরা সমীকরণটি গণনা করি তাহলে আমরা পাব 4+ 1 + |2 - 3| =6. তৃতীয় এবং চতুর্থ পয়েন্টগুলিও শর্ত পূরণ করে এবং 11 + -9 + |6 - 7| =3, তাই সর্বোচ্চ 6।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
বাম :=0, ডানে :=1
-
max_value :=-inf
-
ডানে <বিন্দুর আকার, করুন
-
(xl, yl) :=পয়েন্ট[বাম]
-
(xr, yr) :=পয়েন্ট[ডান]
-
diff :=|xr - xl|
-
যদি বাম ডানের মত হয়, তাহলে
-
ডান:=ডান + 1
-
-
অন্যথায় যখন diff <=k, তারপর
-
m :=yl + yr + পার্থক্য
-
max_value :=max_value এর সর্বোচ্চ এবং m
-
যদি yl>=yr - পার্থক্য হয়, তাহলে
-
ডান:=ডান + 1
-
-
অন্যথায়,
-
left :=left + 1
-
-
অন্যথায়,
-
left :=left + 1
-
-
-
-
রিটার্ন max_value
উদাহরণ
আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি
def solve(points, k): left, right = 0, 1 max_value = float('-inf') while right < len(points): xl, yl = points[left] xr, yr = points[right] diff = abs(xr - xl) if left == right: right += 1 elif diff <= k: m = yl + yr + diff max_value = max(max_value, m) if yl >= yr - diff: right += 1 else: left += 1 else: left += 1 return max_value points = [[2,4],[3,1],[6,11],[7,-9]] k = 1 print(solve(points, k))
ইনপুট
[[2,4],[3,1],[6,11],[7,-9]], 1
আউটপুট
6