দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স#
আমাদের $n$ সংখ্যাবিশিষ্ট একটি অ্যারে দেওয়া আছে: $a[0 \dots n-1]$। কাজ হলো $a$-তে দীর্ঘতম, কঠোরভাবে ক্রমবর্ধমান, সাবসিকোয়েন্স খুঁজে বের করা।
আনুষ্ঠানিকভাবে আমরা ইনডেক্সের দীর্ঘতম ক্রম $i_1, \dots i_k$ খুঁজি যেন
$$i_1 < i_2 < \dots < i_k,\quad a[i_1] < a[i_2] < \dots < a[i_k]$$এই আর্টিকেলে আমরা এই কাজটি সমাধানের জন্য একাধিক অ্যালগরিদম আলোচনা করব। এছাড়াও আমরা কিছু অন্যান্য সমস্যা আলোচনা করব, যেগুলো এই সমস্যায় সরলীকৃত করা যায়।
ডায়নামিক প্রোগ্রামিং দিয়ে $O(n^2)$ সমাধান#
ডায়নামিক প্রোগ্রামিং একটি অত্যন্ত সাধারণ কৌশল যা বিশাল শ্রেণীর সমস্যা সমাধান করতে দেয়। এখানে আমরা আমাদের নির্দিষ্ট কাজের জন্য এই কৌশলটি প্রয়োগ করি।
প্রথমে আমরা শুধু দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজব, এবং পরে শিখব কীভাবে সাবসিকোয়েন্সটি পুনরুদ্ধার করতে হয়।
দৈর্ঘ্য বের করা#
এই কাজ সম্পন্ন করতে, আমরা একটি অ্যারে $d[0 \dots n-1]$ সংজ্ঞায়িত করি, যেখানে $d[i]$ হলো $i$ ইনডেক্সের উপাদানে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য।
Example
$$\begin{array}{ll} a &= \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} \\ d &= \{1, 1, 2, 3, 3, 1, 1, 4, 5, 2\} \end{array}$$ইনডেক্স ৪-এ শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স হলো $\{3, 4, 5\}$ যার দৈর্ঘ্য ৩, ইনডেক্স ৮-এ শেষ হওয়া দীর্ঘতমটি হলো $\{3, 4, 5, 7, 9\}$ বা $\{3, 4, 6, 7, 9\}$, উভয়ের দৈর্ঘ্য ৫, এবং ইনডেক্স ৯-এ শেষ হওয়া দীর্ঘতমটি হলো $\{0, 1\}$ যার দৈর্ঘ্য ২।
তাহলে ধরি বর্তমান ইনডেক্স $i$। অর্থাৎ আমরা $d[i]$-র মান হিসাব করতে চাই এবং পূর্ববর্তী সব মান $d[0], \dots, d[i-1]$ ইতিমধ্যে জানা। তাহলে দুটি বিকল্প আছে:
$d[i] = 1$: প্রয়োজনীয় সাবসিকোয়েন্সে শুধুমাত্র $a[i]$ উপাদানটি আছে।
$d[i] > 1$: সাবসিকোয়েন্স $a[i]$-তে শেষ হবে, এবং এর ঠিক আগে কোনো সংখ্যা $a[j]$ থাকবে যেখানে $j < i$ এবং $a[j] < a[i]$।
সহজেই দেখা যায়, $a[j]$-তে শেষ হওয়া সাবসিকোয়েন্সটি নিজেই $a[j]$-তে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সগুলোর একটি হবে। $a[i]$ সংখ্যাটি সেই দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সকে একটি সংখ্যা দ্বারা প্রসারিত করে।
সুতরাং, আমরা $j < i$ সহ $a[j] < a[i]$ এমন সব $j$ এর উপর ইটারেট করতে পারি, এবং $a[j]$-তে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সে $a[i]$ যোগ করে যে দীর্ঘতম ক্রম পাই সেটি নিতে পারি। $a[j]$-তে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য $d[j]$, একটি দ্বারা প্রসারিত করলে দৈর্ঘ্য $d[j] + 1$ হয়।
$$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$
এই দুটি ক্ষেত্র একত্রিত করলে $d[i]$-র চূড়ান্ত উত্তর পাই:
$$d[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$ইমপ্লিমেন্টেশন#
এখানে উপরে বর্ণিত অ্যালগরিদমের একটি ইমপ্লিমেন্টেশন দেওয়া হলো, যা দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য হিসাব করে।
int lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i])
d[i] = max(d[i], d[j] + 1);
}
}
int ans = d[0];
for (int i = 1; i < n; i++) {
ans = max(ans, d[i]);
}
return ans;
}সাবসিকোয়েন্স পুনরুদ্ধার#
এখনো পর্যন্ত আমরা শুধু সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে শিখেছি, সাবসিকোয়েন্সটি নিজে নয়।
সাবসিকোয়েন্স পুনরুদ্ধার করতে আমরা একটি অতিরিক্ত সহায়ক অ্যারে $p[0 \dots n-1]$ তৈরি করি যা $d[]$ অ্যারের পাশাপাশি হিসাব করব। $p[i]$ হবে $i$-তে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দ্বিতীয় শেষ উপাদানের ইনডেক্স $j$। অন্য কথায় ইনডেক্স $p[i]$ হলো সেই $j$ যেটিতে সর্বোচ্চ $d[i]$ মান পাওয়া গেছে। এই সহায়ক অ্যারে $p[]$ কোনো অর্থে পূর্বসূরীদের দিকে নির্দেশ করে।
তারপর সাবসিকোয়েন্স বের করতে, আমরা সর্বোচ্চ $d[i]$ বিশিষ্ট ইনডেক্স $i$ থেকে শুরু করি এবং সম্পূর্ণ সাবসিকোয়েন্স পাওয়া না পর্যন্ত পূর্বসূরী অনুসরণ করি, অর্থাৎ $d[i] = 1$ এমন উপাদানে পৌঁছানো পর্যন্ত।
পুনরুদ্ধারের ইমপ্লিমেন্টেশন#
আমরা পূর্ববর্তী অনুচ্ছেদের কোড কিছুটা পরিবর্তন করব। আমরা $d[]$-র পাশাপাশি $p[]$ অ্যারে হিসাব করব, এবং তারপর সাবসিকোয়েন্স হিসাব করব।
সুবিধার জন্য আমরা প্রাথমিকভাবে পূর্বসূরীদের $p[i] = -1$ রাখি। $d[i] = 1$ এমন উপাদানের জন্য, পূর্বসূরীর মান $-1$ থাকবে, যা সাবসিকোয়েন্স পুনরুদ্ধারে কিছুটা সুবিধাজনক।
vector<int> lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1), p(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
p[i] = j;
}
}
}
int ans = d[0], pos = 0;
for (int i = 1; i < n; i++) {
if (d[i] > ans) {
ans = d[i];
pos = i;
}
}
vector<int> subseq;
while (pos != -1) {
subseq.push_back(a[pos]);
pos = p[pos];
}
reverse(subseq.begin(), subseq.end());
return subseq;
}সাবসিকোয়েন্স পুনরুদ্ধারের বিকল্প উপায়#
সহায়ক অ্যারে $p[]$ ছাড়াও সাবসিকোয়েন্স পুনরুদ্ধার করা সম্ভব। আমরা কেবল $d[i]$-র বর্তমান মান পুনঃহিসাব করতে পারি এবং সর্বোচ্চ কীভাবে অর্জিত হয়েছে তাও দেখতে পারি।
এই পদ্ধতিতে কোড কিছুটা লম্বা হয়, কিন্তু বিনিময়ে কিছু মেমোরি সাশ্রয় হয়।
ডায়নামিক প্রোগ্রামিং ও বাইনারি সার্চ দিয়ে $O(n \log n)$ সমাধান#
দ্রুততর সমাধান পেতে, আমরা $O(n^2)$-এ চলে এমন একটি ভিন্ন ডায়নামিক প্রোগ্রামিং সমাধান তৈরি করি, এবং পরে $O(n \log n)$-এ উন্নত করি।
আমরা ডায়নামিক প্রোগ্রামিং অ্যারে $d[0 \dots n]$ ব্যবহার করব। এবার $d[l]$ উপাদান $a[i]$ বা অ্যারের প্রিফিক্সের সাথে সংশ্লিষ্ট নয়। $d[l]$ হবে সেই ক্ষুদ্রতম উপাদান যেটিতে $l$ দৈর্ঘ্যের একটি ক্রমবর্ধমান সাবসিকোয়েন্স শেষ হয়।
প্রাথমিকভাবে আমরা ধরি $d[0] = -\infty$ এবং অন্য সব দৈর্ঘ্যের জন্য $d[l] = \infty$।
আমরা আবার ধাপে ধাপে সংখ্যাগুলো প্রসেস করব, প্রথমে $a[0]$, তারপর $a[1]$, ইত্যাদি, এবং প্রতিটি ধাপে $d[]$ অ্যারে হালনাগাদ রাখব।
Example
অ্যারে $a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$ দেওয়া থাকলে, এখানে তাদের সব প্রিফিক্স এবং ডায়নামিক প্রোগ্রামিং অ্যারে। লক্ষ্য করুন, অ্যারের মান সবসময় শেষে পরিবর্তিত হয় না।
$$ \begin{array}{ll} \text{prefix} = \{\} &\quad d = \{-\infty, \infty, \dots\}\\ \text{prefix} = \{8\} &\quad d = \{-\infty, 8, \infty, \dots\}\\ \text{prefix} = \{8, 3\} &\quad d = \{-\infty, 3, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4\} &\quad d = \{-\infty, 3, 4, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6\} &\quad d = \{-\infty, 3, 4, 6, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6, 5\} &\quad d = \{-\infty, 3, 4, 5, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2\} &\quad d = \{-\infty, 2, 4, 5, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0\} &\quad d = \{-\infty, 0, 4, 5, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7\} &\quad d = \{-\infty, 0, 4, 5, 7, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9\} &\quad d = \{-\infty, 0, 4, 5, 7, 9, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} &\quad d = \{-\infty, 0, 1, 5, 7, 9, \infty, \dots \}\\ \end{array} $$আমরা $d[l] = a[i]$ সেট করি, যদি $l$ দৈর্ঘ্যের একটি দীর্ঘতম ক্রমবর্ধমান ক্রম $a[i]$-তে শেষ হয়, এবং $l$ দৈর্ঘ্যের কোনো দীর্ঘতম ক্রমবর্ধমান ক্রম আরো ছোট সংখ্যায় শেষ না হয়। পূর্ববর্তী পদ্ধতির মতো, যদি আমরা $l$ দৈর্ঘ্যের দীর্ঘতম ক্রমবর্ধমান ক্রম থেকে $a[i]$ সরাই, তাহলে $l -1$ দৈর্ঘ্যের আরেকটি দীর্ঘতম ক্রমবর্ধমান ক্রম পাই। তাই আমরা $l - 1$ দৈর্ঘ্যের দীর্ঘতম ক্রমবর্ধমান ক্রমকে $a[i]$ দিয়ে প্রসারিত করতে চাই, এবং স্পষ্টতই সবচেয়ে ছোট উপাদানে শেষ হওয়া $l - 1$ দৈর্ঘ্যের ক্রমটি সবচেয়ে ভালো কাজ করবে, অর্থাৎ $d[l-1]$ উপাদানে শেষ হওয়া $l-1$ দৈর্ঘ্যের ক্রম।
$l - 1$ দৈর্ঘ্যের একটি দীর্ঘতম ক্রমবর্ধমান ক্রম আছে যা আমরা $a[i]$ দিয়ে প্রসারিত করতে পারি, ঠিক তখনই যদি $d[l-1] < a[i]$। তাই আমরা প্রতিটি দৈর্ঘ্য $l$ এর উপর ইটারেট করতে পারি, এবং শর্ত পরীক্ষা করে $l - 1$ দৈর্ঘ্যের ক্রম প্রসারিত করা যায় কিনা দেখতে পারি।
অতিরিক্তভাবে আমাদের পরীক্ষা করতে হবে, হয়তো আমরা ইতিমধ্যে $l$ দৈর্ঘ্যের একটি দীর্ঘতম ক্রমবর্ধমান ক্রম পেয়েছি যা আরো ছোট সংখ্যায় শেষ হয়। তাই আমরা শুধু তখনই আপডেট করি যদি $a[i] < d[l]$।
$a[]$-র সব উপাদান প্রসেস করার পরে কাঙ্ক্ষিত সাবসিকোয়েন্সের দৈর্ঘ্য হলো সবচেয়ে বড় $l$ যেখানে $d[l] < \infty$।
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
for (int l = 1; l <= n; l++) {
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}আমরা এখন দুটি গুরুত্বপূর্ণ পর্যবেক্ষণ করি।
১. $d$ অ্যারে সবসময় সাজানো থাকবে: সব $i = 1 \dots n$ এর জন্য $d[l-1] < d[l]$।
এটি তুচ্ছ, কারণ আপনি $l$ দৈর্ঘ্যের ক্রমবর্ধমান সাবসিকোয়েন্স থেকে শেষ উপাদান সরাতে পারেন, এবং $l-1$ দৈর্ঘ্যের একটি ক্রমবর্ধমান সাবসিকোয়েন্স পান যা আরো ছোট সংখ্যায় শেষ হয়।
২. উপাদান $a[i]$ সর্বাধিক একটি মান $d[l]$ আপডেট করবে।
এটি উপরের ইমপ্লিমেন্টেশন থেকে তৎক্ষণাৎ অনুসরণ করে।
$d[l-1] < a[i] < d[l]$ এমন অ্যারেতে শুধু একটি জায়গা থাকতে পারে।
সুতরাং আমরা বাইনারি সার্চ ব্যবহার করে $O(\log n)$-এ $d[]$ অ্যারেতে এই উপাদান খুঁজতে পারি। আসলে আমরা কেবল $d[]$ অ্যারেতে $a[i]$-র চেয়ে কঠোরভাবে বড় প্রথম সংখ্যা খুঁজতে পারি, এবং উপরের ইমপ্লিমেন্টেশনের মতোই সেই উপাদান আপডেট করার চেষ্টা করি।
ইমপ্লিমেন্টেশন#
এটি আমাদের উন্নত $O(n \log n)$ ইমপ্লিমেন্টেশন দেয়:
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}সাবসিকোয়েন্স পুনরুদ্ধার#
এই পদ্ধতিতেও সাবসিকোয়েন্স পুনরুদ্ধার করা সম্ভব। এবার আমাদের দুটি সহায়ক অ্যারে রাখতে হবে। একটি যেটি $d[]$-তে উপাদানগুলোর ইনডেক্স বলে। এবং আবারও “পূর্বসূরী” $p[i]$-র একটি অ্যারে তৈরি করতে হবে। $p[i]$ হবে $i$ উপাদানে শেষ হওয়া অপটিমাল সাবসিকোয়েন্সের পূর্ববর্তী উপাদানের ইনডেক্স।
$a[]$ অ্যারের উপর ইটারেশনের সময় $d[]$-র হিসাবের পাশাপাশি এই দুটি অ্যারে রাখা সহজ। এবং শেষে এই অ্যারেগুলো ব্যবহার করে কাঙ্ক্ষিত সাবসিকোয়েন্স পুনরুদ্ধার করা কঠিন নয়।
ডেটা স্ট্রাকচার দিয়ে $O(n \log n)$ সমাধান#
$O(n \log n)$-এ দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স হিসাবের উপরের পদ্ধতির বদলে আমরা সমস্যাটি ভিন্নভাবেও সমাধান করতে পারি: কিছু সাধারণ ডেটা স্ট্রাকচার ব্যবহার করে।
আসুন প্রথম পদ্ধতিতে ফিরে যাই। মনে রাখুন $d[i]$ হলো $j < i$ এবং $a[j] < a[i]$ সহ $d[j] + 1$ মান।
সুতরাং যদি আমরা একটি অতিরিক্ত অ্যারে $t[]$ সংজ্ঞায়িত করি যেন
$$t[a[i]] = d[i],$$তাহলে $d[i]$-র মান হিসাবের সমস্যা $t[]$ অ্যারের একটি প্রিফিক্সে সর্বোচ্চ মান খোঁজার সমতুল্য:
$$d[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)$$একটি অ্যারের (যা পরিবর্তিত হয়) প্রিফিক্সের সর্বোচ্চ খোঁজার সমস্যা একটি স্ট্যান্ডার্ড সমস্যা যা বিভিন্ন ডেটা স্ট্রাকচার দিয়ে সমাধান করা যায়। উদাহরণস্বরূপ আমরা একটি সেগমেন্ট ট্রি বা একটি ফেনউইক ট্রি ব্যবহার করতে পারি।
এই পদ্ধতির কিছু স্পষ্ট অসুবিধা আছে: ইমপ্লিমেন্টেশনের দৈর্ঘ্য ও কমপ্লেক্সিটির দিক থেকে এই পদ্ধতি বাইনারি সার্চ ব্যবহারকারী পদ্ধতির চেয়ে খারাপ হবে। এছাড়াও ইনপুট সংখ্যা $a[i]$ বিশেষভাবে বড় হলে, কিছু কৌশল ব্যবহার করতে হবে, যেমন সংখ্যা সংকোচন (অর্থাৎ $0$ থেকে $n-1$ পর্যন্ত পুনঃনম্বরায়ন), অথবা ডায়নামিক সেগমেন্ট ট্রি ব্যবহার করতে হবে (কেবল ট্রির গুরুত্বপূর্ণ শাখাগুলো তৈরি করা)। অন্যথায় মেমোরি খরচ অত্যধিক হবে।
অন্যদিকে এই পদ্ধতির কিছু সুবিধাও আছে: এই পদ্ধতিতে ডায়নামিক প্রোগ্রামিং সমাধানের কোনো জটিল ধর্ম নিয়ে চিন্তা করতে হয় না। এবং এই পদ্ধতি আমাদের সমস্যাটি খুব সহজে সাধারণীকৃত করতে দেয় (নিচে দেখুন)।
সম্পর্কিত সমস্যা#
এখানে কয়েকটি সমস্যা দেওয়া হলো যেগুলো দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স খোঁজার সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত।
দীর্ঘতম অ-হ্রাসমান সাবসিকোয়েন্স#
এটি আসলে প্রায় একই সমস্যা। এবার শুধু সাবসিকোয়েন্সে অভিন্ন সংখ্যা ব্যবহার করার অনুমতি আছে।
সমাধানও প্রায় একই। আমাদের কেবল অসমতার চিহ্ন পরিবর্তন করতে হবে, এবং বাইনারি সার্চে সামান্য পরিবর্তন করতে হবে।
দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের সংখ্যা#
আমরা প্রথম আলোচিত পদ্ধতি ব্যবহার করতে পারি, হয় $O(n^2)$ সংস্করণ বা ডেটা স্ট্রাকচার ব্যবহারকারী সংস্করণ। আমাদের কেবল অতিরিক্তভাবে সংরক্ষণ করতে হবে $d[i]$ মানে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সগুলো কতভাবে পাওয়া যায়।
$a[i]$-তে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স গঠনের উপায়ের সংখ্যা হলো $j$-তে শেষ হওয়া সব দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের উপায়ের যোগফল যেখানে $d[j]$ সর্বোচ্চ। একাধিক এরকম $j$ থাকতে পারে, তাই সবগুলো যোগ করতে হবে।
সেগমেন্ট ট্রি ব্যবহার করে এই পদ্ধতিও $O(n \log n)$-এ ইমপ্লিমেন্ট করা যায়।
এই কাজের জন্য বাইনারি সার্চ পদ্ধতি ব্যবহার করা সম্ভব নয়।
একটি ক্রমকে আচ্ছাদনকারী অ-বর্ধমান সাবসিকোয়েন্সের ন্যূনতম সংখ্যা#
$n$ সংখ্যা $a[0 \dots n - 1]$ বিশিষ্ট একটি প্রদত্ত অ্যারের জন্য আমাদের সংখ্যাগুলোকে ন্যূনতম সংখ্যক রঙে রঙ করতে হবে, যাতে প্রতিটি রঙ একটি অ-বর্ধমান সাবসিকোয়েন্স গঠন করে।
এটি সমাধান করতে, আমরা লক্ষ্য করি যে প্রয়োজনীয় রঙের ন্যূনতম সংখ্যা দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্যের সমান।
প্রমাণ: আমাদের এই দুটি সমস্যার দ্বৈততা প্রমাণ করতে হবে।
ধরি $x$ হলো দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য এবং $y$ হলো একটি আচ্ছাদন গঠনকারী অ-বর্ধমান সাবসিকোয়েন্সের ন্যূনতম সংখ্যা। আমাদের প্রমাণ করতে হবে $x = y$।
স্পষ্টতই $y < x$ সম্ভব নয়, কারণ যদি আমাদের $x$টি কঠোরভাবে ক্রমবর্ধমান উপাদান থাকে, তাহলে কোনো দুটি একই অ-বর্ধমান সাবসিকোয়েন্সের অংশ হতে পারে না। সুতরাং $y \ge x$।
এখন আমরা দেখাব যে $y > x$ সম্ভব নয় বিরোধের মাধ্যমে। ধরি $y > x$। তাহলে আমরা $y$টি অ-বর্ধমান সাবসিকোয়েন্সের যেকোনো অপটিমাল সেট বিবেচনা করি। আমরা এই সেটকে নিম্নলিখিতভাবে রূপান্তরিত করি: যতক্ষণ দুটি সাবসিকোয়েন্স আছে যেন প্রথমটি দ্বিতীয় সাবসিকোয়েন্সের আগে শুরু হয়, এবং প্রথম ক্রমটি দ্বিতীয়ের চেয়ে বড় বা সমান সংখ্যা দিয়ে শুরু হয়, তাহলে আমরা এই শুরুর সংখ্যাটি খুলে দ্বিতীয়টির শুরুতে লাগাই। সসীম সংখ্যক ধাপের পরে আমাদের $y$টি সাবসিকোয়েন্স থাকবে, এবং তাদের শুরুর সংখ্যাগুলো $y$ দৈর্ঘ্যের একটি ক্রমবর্ধমান সাবসিকোয়েন্স গঠন করবে। যেহেতু আমরা ধরেছিলাম $y > x$ আমরা বিরোধে পৌঁছেছি।
সুতরাং $y = x$।
ক্রমগুলো পুনরুদ্ধার: ক্রমের কাঙ্ক্ষিত বিভাজন সাবসিকোয়েন্সে গ্রিডিভাবে করা যায়। অর্থাৎ বাম থেকে ডানে যান এবং বর্তমান সংখ্যাটি সেই সাবসিকোয়েন্সে অ্যাসাইন করুন যেটি ন্যূনতম সংখ্যায় শেষ হয়েছে যা বর্তমান সংখ্যার চেয়ে বড় বা সমান।