أطول متتالية جزئية متزايدة
خوارزمية فعالة للحل

الخوارزمية التالية تحلّ مسألة إيجاد أطول متتالية جزئية متزايدة باستخدام المصفوفات والبحث الثنائي. 
فهي تقوم بمعالجة عناصر المتتالية تباعاً، وتقوم بحفظ أطول متتالية جزئية تم العثور عليها حتى الآن. إذا رمزنا إلى عناصر المتتالية بـ [X[1]، X[0، الخ. فبعد معالجة العنصر [X[i، تكون الخوارزمية قد حفظت قيماً في مصفوفتين:
إضافة لما سبق فإن الخوارزمية تحفظ عدداً L يمثل طول أطول متتالية جزئية متزايدة تم العثور عليها حتى الآن.
في الخوارزمية أدناه سنزيح المصفوفة M بالعنصر [M[0 الذي لن يستخدم للتسهيل (فالمصفوفة تستخدم الترقيم بدءاً من الصفر ).
لاحظ أن المتتالية [[X[M[1]]، X[M[2]]، ...، X[M[L تكون غير متناقصة عند أي نقطة من الخوارزمية، لذلك إذا كان هناك متتالية جزئية طولها i تنتهي عند [[X[M[i
فهناك أيضاً متتالية جزئية طولها i-1 تنتهي عند قيمة أصغر : وهي القيمة [[[X[P[M[i. لذلك نقوم بعمل بحث ثنائي في المتتالية في زمن لوغاريتمي .
سنكتب الخوارزمية بالعربية لتقريبها إلى الفهم أكثر بحيث توضح المسميات وظيفة كل متحول ومصفوفة وذلك كما يلي :
سنرمز بالكلمة أمجد لــأطول متتالية جزئية متزايدة .
[M[j تكافئها : رقم_أصغر_نهاية_لأمجد_بطول_ما[ج]
[P[k تكافئها : رقم_السابق_في_أمجد_لعنصر_ما[ك]
[X[k تكافئها : الدخل[ك]
عدد العناصر N يقابله الحجم
طول أمجد تم العثور عليها L يقابله الطول
نص الخوارزمية بطريقة شبه الكود كما يلي :
رقم_السابق_في_أمجد_لعنصر_ما = مصفوفة طولها الحجم
رقم_أصغر_نهاية_لأمجد_بطول_ما = مصفوفة طولها الحجم+1
الطول = 0

من أجل المتحول س ضمن المجال من 0 إلى الحجم-1 :
 \\ بحث ثنائي للعثور على أكبر قيمة تحقق العلاقتين ج ≤ الطول
 \\ و الدخل[ رقم_أصغر_نهاية_لأمجد_بطول_ما[ج] ] <الدخل[س]
 رقم_القيمة_الأدنى = 1
 رقم_القيمة_الأعلى = الطول
 طالما رقم_القيمة_الأدنى ≤ رقم_القيمة_الأعلى :
  رقم_القيمة_الوسطى = (رقم_القيمة_الأدنى+رقم_القيمة_الأعلى)\2
  إذا كان الدخل[ رقم_أصغر_نهاية_لأمجد_بطول_ما[رقم_القيمة_الوسطى] ] <الدخل[س]:
   رقم_القيمة_الأدنى = رقم_القيمة_الوسطى +1
  وإلا :
   رقم_القيمة_الأعلى = رقم_القيمة_الوسطى -1
  نهاية جملة الشرط
 نهاية حلقة التكرار
   
 \\ بعد انتهاء البحث،رقم_القيمة_الأدنى أكبر بمقدار 1 من
 \\ طول أمجد التي تسبق الدخل[س]
 الطول_الجديد = رقم_القيمة_الأدنى
 \\ العنصر الذي يسبق الدخل[س] في أمجد المنتهية بالدخل[س]
 \\ هو آخر عنصر من أمجد ذات الطول الطول_الجديد -1 
 السابق_في_أمجد_لعنصر_ما[س] = رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد -1 ]
   
 إذا كان الطول_الجديد> الطول :
  \\ أي أننا وجدنا أمجد جديدة أطول من السابقة
  \\ لذلك علينا تحديث قيمة الطول و رقم_أصغر_نهاية_لأمجد_بطول_ما
  رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد] = س
  الطول = الطول_الجديد
 وإلا إذا كان الدخل[س] <الدخل[رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد]]:
  \\ أي أننا عثرنا على قيمة أصغر لنهاية أمجد بطول الطول_الجديد
  \\ فعلينا تغيير هذه القيمة
   رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول_الجديد] = س
 نهاية جملة الشرط 
نهاية حلقة التكرار

\\إعادة بناء أمجد
عناصر_أمجد = مصفوفة طولها الطول
ك = رقم_أصغر_نهاية_لأمجد_بطول_ما[الطول]
من أجل المتحول س في المجال من الطول-1 إلى 0 :
  عناصر_أمجد[س] = الدخل [ك]
  ك = رقم_السابق_في_أمجد_لعنصر_ما[ك]
نهاية حلقة التكرار

قم بإعادة عناصر_أمجد
نهاية الخوارزمية
الزمن الكلي الذي تستغرقه الخوارزمية باستخدام رمز O الكبير هو (O(n log n وذلك لأن الخوارزمية تقوم بعملية بحث ثنائي من أجل كل عنصر .ناقش العالم فريدمان(1975) تعديلات على الخوارزمية نسبها إلى دونالد كنوث ، تختبر خوارزميته المعدلة فيما إذا كان من الممكن استخدام العنصر [X[i لتمديد المتتالية الجزئية الحالية الأطول، وذلك خلال زمن ثابت، وذلك قبل القيام بالبحث الثنائي .
تستخدم الخوارزمية وفق هذا التعديل عدداً أقصى من عمليات المقارنة هو (n log2 n − n log2log2 n + O(n في الحالة الأسوأ، وهو زمن مثالي لخوارزمية تعتمد المقارنة وذلك حتى الوصول إلى الثابت في عبارة (O(n .