सबसे लंबे समय तक बढ़ने वाले सब्सक्रिप्शन

Question

अन्य सीएस समस्याओं से निपटने में एलआईएस (Longest Increasing Subsequence) समस्या कितनी उपयोगी है? धैर्य सॉर्टिंग, गतिशील प्रोग्रामिंग या निर्णय पेड़ के साथ, कुछ एल्गोरिदम हैं। वास्तविक जीवन में इनका उपयोग कैसे किया जाता है - शायद डेटा धाराओं या कुछ के लिए?

आपको याद दिलाना करने के लिए, मैं बोल्ड में डाल सबसे लंबे समय तक बढ़ती अनुक्रम

{, 8, 4, 12, , 10, , 14, 1, , 5 , 13, 3, , 7, }।

बोनस के रूप में, क्या a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n परिणाम का उपयोग करने का कोई तरीका है? जैसे लंबाई 16 के रूप में हमारी सूची, इसलिए लंबाई 5 के बढ़ते अनुक्रम या लंबाई 5 के घटते क्रम होना चाहिए। हमारे मामले में 0,2,6,9,11,15।

इसके अलावा लंबाई 8 की बढ़ती अनुक्रम या लंबाई 3 के घटते अनुक्रम: हमारे मामले में 12,10,1।

Answer 1

एलआईएस की एक दिलचस्प वास्तविक दुनिया आवेदन धैर्य Diff, एक diffing एल्गोरिथ्म Bram Cohen द्वारा (बिट टोरेंट के निर्माता) जो Bazaar संस्करण नियंत्रण प्रणाली में इस्तेमाल किया जाता है।

नियमित diff एल्गोरिदम में दो दस्तावेज़ों के बीच एलसीएस (Longest Common Subsequence) की गणना करना शामिल है। कुशल होने के दौरान, इस दृष्टिकोण में एक समस्या है, जो है - परिणाम अक्सर मानव-अनुकूल नहीं होते हैं।

कैसे एक नियमित रूप से diff विफल हो सकता है की एक साधारण उदाहरण:

void func1() { 
    x += 1 
+} 
+ 
+void functhreehalves() { 
+ x += 1.5 
} 

void func2() { 
    x += 2 
} 

धैर्य Diff एल्गोरिथ्म के लाभ यह है कि इसे और अधिक बारीकी कैसे एक इंसान के लिए इसी तरीके से, और अधिक सही मतभेद की गणना करने की अनुमति देता है प्रदर्शन करेंगे

पिछले मामले धैर्य Diff में अंतर बेहतर देखती है:

void func1() { 
    x += 1 
} 

+void functhreehalves() { 
+ x += 1.5 
+} 
+ 
void func2() { 
    x += 2 
} 

संक्षेप में, एल्गोरिथ्म है:

1. अद्वितीय लाइनों जो दोनों दस्तावेजों के लिए आम हैं का पता लगाएं।
2. पहले दस्तावेज़ से ऐसी सभी पंक्तियां लें और उन्हें दूसरे दस्तावेज़ में उनकी उपस्थिति के अनुसार आदेश दें।
3. परिणामी अनुक्रम के एलआईएस की गणना करें (Patience Sort करके), लाइनों का सबसे लंबा मिलान अनुक्रम प्राप्त करना, दो दस्तावेज़ों की रेखाओं के बीच एक पत्राचार।
4. पहले से मेल खाने वाले लोगों के बीच की प्रत्येक पंक्ति पर एल्गोरिदम की पुनरावृत्ति करें।

the code पर एक नज़र डालें।