इस समस्या में, हमें एक स्ट्रिंग दी गई है जो एक बड़ी संख्या को दर्शाती है और एक पूर्णांक 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
