समस्या और प्रयोज्य परिदृश्य
एक पूर्णांक ऐरे nums दिया गया है, कोई भी सबसे लंबा कड़ाई से बढ़ता हुआ उप-अनुक्रम (strictly increasing subsequence) लौटाएं। एक उप-अनुक्रम इनपुट के सापेक्ष क्रम को बनाए रखता है लेकिन उसका सन्निहित होना आवश्यक नहीं है। "कड़ाई से बढ़ता हुआ" का अर्थ है कि प्रत्येक अगला मान बड़ा होना चाहिए, इसलिए समान मान लंबाई को नहीं बढ़ा सकते। यदि कई इष्टतम उत्तर मौजूद हैं, तो कोई भी एक लौटाएं। खाली इनपुट के लिए एक खाली ऐरे लौटाएं।
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 18]
Increasing indices: 2 < 4 < 5 < 7
Increasing values: 2 < 3 < 7 < 18
Length: 4मान लें 0 ≤ n ≤ 100,000, हस्ताक्षरित 32-बिट पूर्णांक मान, और एक इनपुट ऐरे जिसे अपरिवर्तित रहना चाहिए। यह पैमाना उप-अनुक्रमों की गणना (enumeration) को खारिज करता है और अंतिम समाधान के रूप में द्विघातीय (quadratic) डायनेमिक प्रोग्रामिंग को बाहर करता है। LeetCode समस्या एक कड़ाई से बढ़ते उप-अनुक्रम की लंबाई मांगती है और स्पष्ट रूप से O(n log n) लक्ष्य के साथ फॉलो-अप करती है। अप्रैल 2026 का एक सार्वजनिक इंटरव्यू-तैयारी लेख अभी भी द्विघातीय DP और बाइनरी-सर्च ऑप्टिमाइज़ेशन दोनों सिखाता है। यह संस्करण अतिरिक्त रूप से एक वास्तविक उप-अनुक्रम लौटाता है। वे स्रोत समस्या और इसके वर्तमान तैयारी मूल्य को स्थापित करते हैं; वे इंटरव्यू आवृत्ति या कंपनी एट्रिब्यूशन स्थापित नहीं करते हैं।
साक्षात्कारकर्ता क्या मूल्यांकन करता है
पहला संकेत एक सटीक स्थिति परिभाषा (state definition) है। द्विघातीय समाधान को dp[i] को सर्वोत्तम लंबाई के रूप में परिभाषित करना चाहिए जो अनिवार्य रूप से nums[i] पर समाप्त होनी चाहिए। केवल "पहले i मानों के लिए उत्तर" कहने से वह अंतिम मान छूट जाता है जो यह तय करने के लिए आवश्यक है कि वर्तमान तत्व को जोड़ा जा सकता है या नहीं।
दूसरा संकेत बाधा (bottleneck) से ऑप्टिमाइज़ेशन प्राप्त करना है। प्रत्येक i के लिए प्रत्येक पुराने j को स्कैन करने में O(n²) की लागत आती है। एक मजबूत उत्तर स्थिति को बदल देता है: प्रत्येक प्राप्त करने योग्य लंबाई के लिए, केवल सबसे छोटा अंतिम मान बनाए रखें। एक छोटी टेल (tail) को विस्तारित करना कम से कम उतना ही आसान है। ये न्यूनतम टेल्स कड़ाई से बढ़ते क्रम में होती हैं, इसलिए अपडेट स्थिति को बाइनरी सर्च से खोजा जा सकता है।
तीसरा संकेत डुप्लिकेट्स को सही ढंग से संभालना है। एक कड़ाई से बढ़ते अनुक्रम के लिए पहली ऐसी स्थिति की आवश्यकता होती है जिसकी टेल वर्तमान मान से अधिक या उसके बराबर हो: लोअर-बाउंड सेमेंटिक्स। एक समान मान उसी स्थिति को बदल देता है और लंबाई का विस्तार नहीं करता है। केवल एक गैर-घटती (non-decreasing) भिन्नता उस स्थिति का उपयोग करती है जो मान से कड़ाई से बड़ी हो।
चौथा संकेत यह जानना है कि tails स्वयं उत्तर नहीं है। [3, 5, 6, 2] के बाद, टेल मान [2, 5, 6] हैं। वे मान के अनुसार बढ़ते हैं, लेकिन उनके इनपुट इंडेक्स 3, 1, 2 हैं, इसलिए वे एक उप-अनुक्रम नहीं हैं। एक वास्तविक पथ लौटाने के लिए, प्रत्येक टेल की लंबाई के लिए वर्तमान इनपुट इंडेक्स और प्रत्येक तत्व के लिए एक पूर्ववर्ती इंडेक्स (predecessor index) भी संग्रहीत करें।
अंतिम संकेत प्रमाण और सत्यापन है। एक उम्मीदवार को न्यूनतम-टेल इनवेरिएंट की व्याख्या करनी चाहिए, क्यों प्रतिस्थापन एक इष्टतम लंबाई को नहीं खो सकता है, क्यों पूर्ववर्ती लिंक एक वैध पथ बनाते हैं, और केवल एक उदाहरण पर भरोसा करने के बजाय O(n²) ओरेकल के विरुद्ध यादृच्छिक छोटे इनपुट की तुलना कैसे करें।
उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न
- कड़ाई से बढ़ता हुआ (strictly increasing) या गैर-घटता हुआ (non-decreasing)? यह समस्या सख्त है, इसलिए डुप्लिकेट उत्तर का विस्तार नहीं कर सकते। यदि समानता की अनुमति है, तो बाइनरी-सर्च की सीमा बदल जाती है।
- लंबाई लौटानी है या वास्तविक अनुक्रम? यह समस्या एक अनुक्रम लौटाती है, इसलिए इसे
previousऔर टेल इंडेक्स की आवश्यकता होती है। केवल लंबाई वाला समाधान सहायक स्पेस कोO(L)तक कम कर सकता है, जहाँLउत्तर की लंबाई है। - इष्टतम उत्तरों के बीच टाई का समाधान कैसे किया जाना चाहिए? कोई भी उत्तर स्वीकार्य है। लेक्सिकोग्राफ़िकल रूप से सबसे छोटे, सबसे छोटे-इंडेक्स, या स्थिर चयन आवश्यकताओं के लिए अतिरिक्त नियमों और प्रमाण की आवश्यकता होती है।
- इनपुट का आकार क्या है? एक लाख तत्वों पर,
O(n log n)का उपयोग करें। कुछ सौ तत्वों के लिए, द्विघातीय DP को लागू करना, समझाना और गिनती तक विस्तारित करना आसान है। - क्या इनपुट खाली हो सकता है? हाँ;
[]लौटाएं। यह निर्धारित करता है कि क्या पुनर्निर्माण (reconstruction) अंतिम टेल इंडेक्स को पढ़ सकता है। - क्या इनपुट को संशोधित किया जा सकता है? नहीं। सॉर्टिंग मूल इंडेक्स क्रम को नष्ट कर देती है और समस्या को बदल देती है।
- क्या पूर्णांक अंकगणित ओवरफ्लो हो सकता है? एल्गोरिदम उन पर अंकगणित किए बिना मानों की तुलना और प्रतिलिपि बनाता है, इसलिए एल्गोरिदम के कारण हस्ताक्षरित 32-बिट इनपुट ओवरफ्लो नहीं होते हैं।
30-सेकंड उत्तर ढांचा
"मैं प्रत्येक प्राप्त करने योग्य लंबाई के लिए सबसे छोटी टेल रखता हूँ। वे टेल्स सॉर्ट की गई हैं, इसलिए प्रत्येक मान के लिए मैं बाइनरी सर्च के माध्यम से इसके बराबर या उससे बड़ी पहली टेल ढूंढता हूँ, उस स्थिति को बदलता हूँ, या अंत में जोड़ता हूँ। यह लोअर बाउंड डुप्लिकेट्स को एक सख्त अनुक्रम का विस्तार करने से रोकता है। टेल ऐरे असंगत इनपुट इंडेक्स को मिला सकता है, इसलिए मैं प्रत्येक टेल का इंडेक्स और प्रति तत्व एक पूर्ववर्ती भी संग्रहीत करता हूँ, फिर पीछे की ओर पुनर्निर्माण करता हूँ। प्रति तत्व एक बाइनरी सर्च O(n log n) समय और O(n) स्पेस देती है। मैं एक द्विघातीय ओरेकल के विरुद्ध खाली, डुप्लिकेट, घटते और यादृच्छिक छोटे ऐरे का परीक्षण करता हूँ।"
चरण-दर-चरण गहन समाधान
उस आधार रेखा से शुरुआत करें जिसे सिद्ध करना सबसे आसान है। मान लें कि dp[i] सबसे लंबे कड़ाई से बढ़ते उप-अनुक्रम की लंबाई है जो अनिवार्य रूप से nums[i] पर समाप्त होनी चाहिए। एक से अधिक लंबे किसी भी उत्तर में nums[j] < nums[i] के साथ किसी j < i पर एक उप-अंतिम (penultimate) तत्व होता है:
dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])यह परिभाषा पुनरावृत्ति (recurrence) को भी सिद्ध करती है। प्रत्येक योग्य पूर्ववर्ती को nums[i] द्वारा विस्तारित किया जा सकता है, जबकि nums[i] पर समाप्त होने वाले प्रत्येक इष्टतम अनुक्रम को उन पूर्ववर्तियों में से एक से ट्रांज़िशन करना होगा। समस्या यह है कि प्रत्येक i सभी पिछली स्थितियों को स्कैन करता है, जिसमें कुल O(n²) समय लगता है।
ऑप्टिमाइज़ेशन के लिए, इस प्रीफिक्स इनवेरिएंट को बनाए रखें: पहले i तत्वों को संसाधित करने के बाद, tails[k] लंबाई k + 1 के सभी कड़ाई से बढ़ते उप-अनुक्रमों के बीच सबसे छोटा संभव अंतिम मान है। वर्तमान मान x के लिए, tails[k] ≥ x को संतुष्ट करने वाली पहली स्थिति का पता लगाएं:
- यदि कोई स्थिति मौजूद नहीं है, तो
xप्रत्येक टेल से अधिक है और सबसे लंबे अनुक्रम को एक से विस्तारित करता है। - यदि स्थिति
kमौजूद है, तोtails[k]कोxसे बदलें। लंबाई अपरिवर्तित रहती है, लेकिन एक छोटी या बराबर टेल भविष्य के विस्तार विकल्पों को कम नहीं कर सकती है। - क्योंकि
tailsकड़ाई से बढ़ रहा है, स्थितिO(log L)समय में पाई जाती है।
[3, 5, 6, 2] के लिए, पहली तीन स्थितियाँ [3], [3, 5], और [3, 5, 6] हैं। अंतिम 2 पहली स्थिति को प्रतिस्थापित करता है, जिससे [2, 5, 6] बनता है। लंबाई सही रहती है, लेकिन 2 इनपुट में 5 और 6 के बाद आता है। यह सीधे tails को वापस करने का प्रति-उदाहरण (counterexample) है।
पुनर्निर्माण के लिए दो इंडेक्स संरचनाओं की आवश्यकता होती है। tailsIndices[k] उस इनपुट स्थिति को संग्रहीत करता है जो वर्तमान में लंबाई k + 1 के लिए न्यूनतम टेल को साकार कर रही है। जब nums[i] स्थिति k पर आता है, तो previous[i] को tailsIndices[k - 1] पर सेट करें। वह पूर्ववर्ती i से पहले आता है और उसका मान कड़ाई से छोटा होता है। बाद के टेल प्रतिस्थापन पहले से लिखे गए पूर्ववर्ती लिंक को संशोधित नहीं करते हैं। अंतिम सबसे लंबी टेल से पीछे की ओर पुनर्निर्माण करें।
export function longestIncreasingSubsequence(nums: number[]): number[] {
if (nums.length === 0) return []
const tails: number[] = []
const tailsIndices: number[] = []
const previous = new Array<number>(nums.length).fill(-1)
for (let index = 0; index < nums.length; index += 1) {
const value = nums[index]
let left = 0
let right = tails.length
while (left < right) {
const middle = left + Math.floor((right - left) / 2)
if (tails[middle] < value) left = middle + 1
else right = middle
}
const lengthIndex = left
if (lengthIndex > 0) {
previous[index] = tailsIndices[lengthIndex - 1]
}
if (lengthIndex === tails.length) {
tails.push(value)
tailsIndices.push(index)
} else {
tails[lengthIndex] = value
tailsIndices[lengthIndex] = index
}
}
const result = new Array<number>(tails.length)
let index = tailsIndices[tails.length - 1]
for (
let resultIndex = result.length - 1;
resultIndex >= 0;
resultIndex -= 1
) {
result[resultIndex] = nums[index]
index = previous[index]
}
return result
}शुद्धता के तीन भाग हैं। पहला, tails कड़ाई से बढ़ता रहता है: एक लंबे बढ़ते अनुक्रम से अंतिम आइटम को हटाने पर एक छोटी टेल के साथ एक छोटा अनुक्रम बचता है। दूसरा, बाइनरी-सर्च प्रतिस्थापन प्रत्येक लंबाई के लिए सबसे छोटी प्राप्त करने योग्य टेल को संरक्षित करता है; यह एक लंबा अनुक्रम गढ़े बिना विस्तारशीलता में सुधार करता है। तीसरा, प्रत्येक tailsIndices[k] कड़ाई से बढ़ते पूर्ववर्ती इंडेक्स और मानों के साथ लंबाई k + 1 की एक श्रृंखला का निर्माण करता है। इसलिए tails.length वास्तविक इष्टतम से अधिक नहीं हो सकता है, और किसी भी वास्तविक LIS को स्कैन करने से संरचना को कम से कम उस लंबाई तक पहुंचने के लिए मजबूर होना पड़ता है। पुनर्निर्मित पूर्ववर्ती श्रृंखला एक वैध इष्टतम उत्तर है।
प्रत्येक तत्व अधिकतम L टेल्स पर एक बाइनरी सर्च करता है, जिसके लिए O(n log L) समय और पारंपरिक ऊपरी सीमा O(n log n) है। तीनों ऐरे O(n) स्पेस का उपयोग करते हैं; आउटपुट स्वयं O(L) का उपयोग करता है। एल्गोरिदम न तो इनपुट को सॉर्ट करता है और न ही संख्यात्मक सीमा पर निर्भर करता है।
परीक्षणों को लंबाई, सख्त वृद्धि और इनपुट-इंडेक्स क्रम की जांच करनी चाहिए:
const cases: Array<[number[], number]> = [
[[10, 9, 2, 5, 3, 7, 101, 18], 4],
[[0, 1, 0, 3, 2, 3], 4],
[[7, 7, 7, 7], 1],
[[5, 4, 3, 2, 1], 1],
[[], 0],
]
for (const [nums, expectedLength] of cases) {
const result = longestIncreasingSubsequence(nums)
if (result.length !== expectedLength) throw new Error("wrong length")
for (let i = 1; i < result.length; i += 1) {
if (result[i - 1] >= result[i]) throw new Error("not increasing")
}
}एक अधिक मजबूत जांच अधिकतम 12 लंबाई के यादृच्छिक ऐरे उत्पन्न करती है और एक O(n²) DP ओरेकल के साथ अनुकूलित परिणाम लंबाई की तुलना करती है। इनपुट के माध्यम से एक रैखिक स्कैन को यह भी सत्यापित करना चाहिए कि लौटाए गए मान क्रम में दिखाई देते हैं। साथ में ये जांचें डुप्लिकेट-सीमा त्रुटियों, गलत बाइनरी-सर्च स्थितियों और टूटे हुए पूर्ववर्तियों को उजागर करती हैं।
उच्च गुणवत्ता वाला नमूना उत्तर
"मैं पहले पुष्टि करूंगा कि क्रम सख्त है और मुझे एक वास्तविक अनुक्रम वापस करना होगा। द्विघातीय समाधान dp[i] को nums[i] पर समाप्त होने वाली सर्वोत्तम लंबाई के रूप में परिभाषित करता है और प्रत्येक छोटे पूर्ववर्ती की जांच करता है। उस बैकवर्ड स्कैन को समाप्त करने के लिए, मैं प्रत्येक लंबाई के लिए सबसे छोटी संभव टेल संग्रहीत करता हूँ।
एक मान x के लिए, मुझे x से अधिक या उसके बराबर पहली टेल मिलती है। यदि कोई मौजूद नहीं है, तो x वर्तमान सबसे लंबे अनुक्रम का विस्तार करता है। अन्यथा, उस टेल को x से बदलने से उसी लंबाई को एक ऐसा मान मिलता है जिसे विस्तारित करना कम से कम उतना ही आसान होता है। सख्त वृद्धि के लिए इस लोअर-बाउंड स्थिति की आवश्यकता होती है, इसलिए एक डुप्लिकेट विस्तार करने के बजाय प्रतिस्थापित करता है।
टेल मान प्रत्येक लंबाई के लिए सर्वोत्तम समाप्ति का सारांश देते हैं; उनका संगत इनपुट इंडेक्स से आना आवश्यक नहीं है। एक वास्तविक उत्तर लौटाने के लिए, tailsIndices[k] लंबाई k + 1 के लिए वर्तमान टेल इंडेक्स रिकॉर्ड करता है। जब कोई तत्व स्थिति k पर आता है, तो उसका पूर्ववर्ती tailsIndices[k - 1] होता है। स्कैन के बाद, मैं सबसे लंबी टेल से पूर्ववर्तियों का अनुसरण करता हूँ और आउटपुट को पीछे की ओर भरता हूँ।
इनवेरिएंट यह है कि प्रत्येक टेल अपनी लंबाई के लिए सबसे छोटी प्राप्त करने योग्य टेल है, और प्रत्येक टेल इंडेक्स में एक वास्तविक पूर्ववर्ती श्रृंखला है। प्रतिस्थापन कभी भी किसी मौजूदा लंबाई को नहीं हटाता है और केवल भविष्य के विस्तार में सुधार करता है। इसके विपरीत, किसी भी वास्तविक बढ़ते उप-अनुक्रम के प्रत्येक तत्व को स्कैन करने से संरचना को कम से कम उस लंबाई तक पहुंचने के लिए मजबूर होना पड़ता है, इसलिए अंतिम लंबाई इष्टतम होती है। प्रति तत्व एक बाइनरी सर्च O(n log n) समय देती है, और इंडेक्स प्लस पूर्ववर्ती O(n) स्पेस का उपयोग करते हैं। मैं खाली, डुप्लिकेट, बढ़ते और घटते इनपुट का परीक्षण करूंगा, फिर एक द्विघातीय ओरेकल के साथ यादृच्छिक छोटे ऐरे की तुलना करूंगा।"
सामान्य गलतियाँ
- एक उप-अनुक्रम को एक सन्निहित सब-ऐरे मानना → एक स्लाइडिंग विंडो तत्वों को छोड़ नहीं सकती है → बढ़ते इनपुट इंडेक्स द्वारा उत्तर को परिभाषित करें।
- हल करने से पहले सॉर्ट करना → सॉर्टिंग मूल सापेक्ष क्रम को नष्ट कर देती है → इनपुट क्रम में मानों को प्रोसेस करें।
dp[i]को एक प्रीफिक्स ऑप्टिमम के रूप में परिभाषित करना और सीधे ट्रांज़िशन करना → ऑप्टिमम की टेल वर्तमान मान को स्वीकार नहीं कर सकती है → स्थिति कोiपर समाप्त होने की आवश्यकता रखें।- सख्त संस्करण में मान से कड़ाई से बड़ी पहली टेल की खोज करना → डुप्लिकेट गलत तरीके से लंबाई का विस्तार करते हैं → मान से अधिक या उसके बराबर पहली टेल की खोज करें।
- सीधे
tailsलौटाना → टेल मान घटते इनपुट इंडेक्स से आ सकते हैं → टेल इंडेक्स और पूर्ववर्ती लिंक के साथ पुनर्निर्माण करें। - टेल प्रतिस्थापन के बाद पुराने पूर्ववर्तियों को फिर से लिखना → एक पूर्व मान्य पथ दूषित हो जाता है → असाइनमेंट के बाद प्रत्येक पूर्ववर्ती को अपरिवर्तनीय रखें।
- केवल यह साबित करना कि टेल्स सॉर्ट की गई हैं → केवल सॉर्टेड होना इष्टतम लंबाई साबित नहीं करता है → न्यूनतम प्राप्त करने योग्य टेल इनवेरिएंट और दोनों लंबाई सीमाओं को साबित करें।
- बाइनरी सर्च प्लस ऐरे इंसर्शन को
O(log n)कहना → मध्य इंसर्शन तत्वों को शिफ्ट करता है → केवल उसी स्थान पर बदलें (in-place) या अंत में जोड़ें। - केवल क्लासिक उदाहरण चलाना → डुप्लिकेट और पूर्ववर्ती बग छिपे रहते हैं → सभी-समान, घटते, खाली और यादृच्छिक ओरेकल परीक्षणों का उपयोग करें।
- किसी नामित कंपनी में उच्च आवृत्ति का दावा करना → सार्वजनिक समस्या पृष्ठ आवृत्ति या एट्रिब्यूशन साबित नहीं करते हैं → केवल सत्यापित समस्या और एल्गोरिदम मूल्य बताएं।
फॉलो-अप और उत्तर
फॉलो-अप 1: सबसे लंबे गैर-घटते उप-अनुक्रम के लिए क्या बदलता है?
समान मान अब अनुक्रम का विस्तार कर सकते हैं। सीमा को value से कड़ाई से बड़ी पहली स्थिति में बदलें, जो कि सही इंसर्शन पॉइंट है। पूर्ववर्ती, पुनर्निर्माण और जटिलता समान रहती है। बाइनरी-सर्च सीमा को बदले बिना केवल अंतिम तुलना बदलने से डुप्लिकेट्स पर विफलता होती है।
फॉलो-अप 2: क्या केवल लंबाई वाला उत्तर कम स्पेस का उपयोग कर सकता है?
हाँ। tailsIndices और previous को हटा दें, और O(L) स्पेस के लिए केवल L न्यूनतम टेल मान बनाए रखें। समय O(n log L) बना रहता है। एक अनुक्रम लौटाने के लिए पहले से ही O(L) आउटपुट की आवश्यकता होती है, जबकि यह वन-पास पुनर्निर्माण प्रत्येक इनपुट स्थिति के लिए पूर्ववर्ती जानकारी का उपयोग करता है।
फॉलो-अप 3: आप सबसे लंबे बढ़ते उप-अनुक्रमों की संख्या की गणना कैसे करते हैं?
न्यूनतम टेल्स समान लंबाई के कई पथों को मर्ज करती हैं, इसलिए वे सीधे काउंट को पुनर्प्राप्त नहीं कर सकती हैं। एक सरल समाधान length[i] और count[i] को बनाए रखता है: जब एक लंबा पथ मिलता है तो पूर्ववर्ती काउंट की प्रतिलिपि बनाएं और जब एक समान लंबाई का पथ मिलता है तो काउंट जोड़ें, जिसके लिए O(n²) समय लगता है। बड़े इनपुट मानों को कोऑर्डिनेट-कंप्रेस कर सकते हैं और अधिकतम-लंबाई-और-काउंट युग्म संग्रहीत करने वाले फेनविक ट्री या सेगमेंट ट्री का उपयोग कर सकते हैं, जिसमें डबल काउंटिंग से बचने के लिए सावधानीपूर्वक मर्ज नियम होते हैं।
फॉलो-अप 4: क्या होगा यदि मान केवल-जोड़ने वाली स्ट्रीम (append-only stream) में आते हैं?
वर्तमान LIS लंबाई ऑनलाइन है: O(log L) समय में प्रत्येक आने वाले मान के लिए बाइनरी-सर्च tails करें। यदि एक वास्तविक अनुक्रम उपलब्ध होना चाहिए तो इंडेक्स और पूर्ववर्तियों को बनाए रखें। यदि पुराने मानों को हटाया जा सकता है, तो एक न्यूनतम टेल हटाए गए डेटा पर निर्भर हो सकती है; यह एल्गोरिदम उस स्थिति को स्थानीय रूप से पूर्ववत (undo) नहीं कर सकता है, इसलिए गतिशील संरचनाओं या ऑफ़लाइन अपघटन (offline decomposition) की आवश्यकता होती है।
फॉलो-अप 5: क्या होगा यदि प्रत्येक तत्व का एक भार (weight) हो और लक्ष्य अधिकतम कुल भार हो?
एक न्यूनतम टेल अब स्थिति का सारांश नहीं देती है क्योंकि समान टेल रेंज विभिन्न संचित भार ले जा सकती है। मानों को कोऑर्डिनेट-कंप्रेस करें, छोटे मानों के बीच सर्वोत्तम भार के लिए फेनविक ट्री या सेगमेंट ट्री से क्वेरी करें, वर्तमान भार जोड़ें, और वर्तमान निर्देशांक को अपडेट करें। सख्त और गैर-घटती किस्में अभी भी विभिन्न क्वेरी सीमाओं का उपयोग करती हैं। समय O(n log n) है।
फॉलो-अप 6: क्या यह कोड लेक्सिकोग्राफ़िकल रूप से सबसे छोटा इष्टतम उत्तर लौटाता है?
यह इसकी गारंटी नहीं देता है। प्रतिस्थापन नियम व्यक्तिगत टेल मानों को कम करता है लेकिन पूर्ण इष्टतम पथों के बीच कोई स्थिर क्रम परिभाषित नहीं करता है। एक दृष्टिकोण यह गणना करता है कि प्रत्येक इंडेक्स कितने इष्टतम प्रीफिक्स या सफ़िक्स का समर्थन कर सकता है, फिर लालची रूप से (greedily) उन मानों का चयन करता है जो अभी भी एक इष्टतम-लंबाई उत्तर पूरा कर सकते हैं। सबसे छोटा-मान अनुक्रम और सबसे छोटा-इंडेक्स अनुक्रम अलग-अलग आवश्यकताएं हैं, इसलिए पहले स्पष्ट करें कि कौन सा लेक्सिकोग्राफ़िक क्रम अभीष्ट है।