এই সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া আছে যা একটি বড় সংখ্যা নির্দেশ করে এবং একটি INTEGER k যা ব্রেকপয়েন্টের সংখ্যা নির্দেশ করে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা একটি সংখ্যায় L ব্রেকপয়েন্ট বসিয়ে সর্বোচ্চ সেগমেন্ট ভ্যালু বের করবে।
এখানে, আমাদের সেই সর্বোচ্চ সংখ্যা বের করতে হবে যা k ব্রেকপয়েন্ট বসিয়ে স্ট্রিং দ্বারা দেওয়া সংখ্যাতেই তৈরি করা যায়।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই
ইনপুট − string = “45972”, k = 3
আউটপুট − 97
ব্যাখ্যা −
সম্ভব সব সংখ্যা: 45 9 7 2 4 59 7 2 4 5 97 2 4 5 9 72 এই সব থেকে 97 সবচেয়ে বড় সংখ্যা।
এই সমস্যা সমাধানের জন্য, আমরা স্লাইডিং উইন্ডো টেকনিক ব্যবহার করব। এখানে, উইন্ডো সাইজ হবে (স্ট্রিংয়ের দৈর্ঘ্য - k) অর্থাৎ সর্বোচ্চ সংখ্যাটি এই সাইজের হবে। আমরা স্লাইডিং উইন্ডো টেকনিক ব্যবহার করে এই সাইজের সব সম্ভাব্য সংখ্যা থেকে সর্বোচ্চ সংখ্যা বের করব।
উদাহরণ
একটি সংখ্যায় K ব্রেকপয়েন্ট বসিয়ে সর্বোচ্চ সেগমেন্ট ভ্যালু বের করার প্রোগ্রাম −
#include <bits/stdc++.h> using namespace std; int findMaxSegmentWithKbreaks(string &s, int k) { int window = s.length() - k; int MaxNumber = 0; for (int i=0; i<window; i++) MaxNumber = MaxNumber * 10 + (s[i] - '0'); int slWindow = pow(10, window-1); int value = MaxNumber; for (int i = 1; i <= (s.length() - window); i++) { value = value - (s[i-1]- '0')*slWindow; value = value*10 + (s[i+window-1]- '0'); MaxNumber = max(MaxNumber, value); } return MaxNumber; } int main() { string s = "45972"; int k = 3; cout<<"Maximum segment value after putting "<<k<<" break points in a number = "<<findMaxSegmentWithKbreaks(s, k); return 0; }
আউটপুট
Maximum segment value after putting 3 breakpoints in a number = 97
