أطول متتالية جزئية متزايدة
أطول متتالية جزئية متزايدة في علم الحاسوب، تعالج مسألةُ إيجاد البحث عن متتالية جزئية من متتالية معطاة بحيث تكون عناصر هذه المتتالية الجزئية مرتبة،تصاعديّاً أو تنازليًّا، وبحيث تكون أطول ما يمكن .وهذه المتتالية الجزئية ليست بالضرورة ناتجة عن عناصر متجاورة كما أنها يمكن ألا تكون وحيدة ضمن المتتالية الأصلية.
تمت دراسة مسألة إيجاد أطول متتالية جزئية متزايدة في سياق دراسة عدة فروع متعلقة بالرياضيات، متضمنة الخوارزميات ، تجمع مصفوفة غاوسية،نظرية تمثيل الزمر، والفيزياء. يمكن حل مسألة إيجاد أطول متتالية جزئية متزايدة في زمن( O("n" log "n"، حيث "n" هو طول متتالية الدخل .
في متتالية ڤان دير كورپت الثنائية
إحدى المتتاليات الجزئية الأطول المتزايدة هي
طول هذه المتتالية الجزئية هو 6; أي أن المتتالية الأصلية لا تحوي متتالية جزئية من 7 عناصر يمكنها تشكيل متتالية جزئية متزايدة.كما أن المتتالية الجزئية المتزايدة الأطول ليست وحيدة فمثلاً لدينا 
هما متتاليتان جزئيتان متزايدتان من نفس طول المتتالية الجزئية المتزايدة الأطول .
مسألة إيجاد المتتالية الجزئية المتزايدة الأطول لها تعلق وطيد بمسألة إيجاد أطول متتالية جزئية مشتركة، والتي تحتاج زمناً من الدرجة الثالثة لحلها باستخدام البرمجة الديناميكية : إن أطول متتالية جزئية متزايدة في متتالية ما "S" هي أطول متتالية جزئية مشتركة بين المتتاليتين "S" و "T"، حيث "T" هي نتيجة ترتيب المتتالية "S".
من أجل الحالة الخاصة التي يكون فيها الدخل عبارة عن تبديل للأعداد الصحيحة 1، 2، ...، "n"، يمكن لهذا الحل أن يكون فعالاً ، ليعطينا حلاً بحدود( O("n" log log "n".
الخوارزمية التالية تحلّ مسألة إيجاد أطول متتالية جزئية متزايدة باستخدام المصفوفات والبحث الثنائي. 
فهي تقوم بمعالجة عناصر المتتالية تباعاً، وتقوم بحفظ أطول متتالية جزئية تم العثور عليها حتى الآن. إذا رمزنا إلى عناصر المتتالية بـ [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". لذلك نقوم بعمل بحث ثنائي في المتتالية في زمن لوغاريتمي .
سنكتب الخوارزمية بالعربية لتقريبها إلى الفهم أكثر بحيث توضح المسميات وظيفة كل متحول ومصفوفة وذلك كما يلي :
نص الخوارزمية بطريقة شبه الكود كما يلي :
الزمن الكلي الذي تستغرقه الخوارزمية باستخدام [[رمز O الكبير]] هو (O(n log n وذلك لأن الخوارزمية تقوم بعملية بحث ثنائي من أجل كل عنصر .ناقش العالم فريدمان(1975) تعديلات على الخوارزمية نسبها إلى [[دونالد كنوث]] ، تختبر خوارزميته المعدلة فيما إذا كان من الممكن استخدام العنصر [X[i لتمديد المتتالية الجزئية الحالية الأطول ، وذلك خلال زمن ثابت ، وذلك قبل القيام بالبحث الثنائي .
تستخدم الخوارزمية وفق هذا التعديل عدداً أقصى من عمليات المقارنة هو (n log n − n loglog n + O(n في الحالة الأسوأ ، وهو زمن مثالي لخوارزمية تعتمد المقارنة وذلك حتى الوصول إلى الثابت في عبارة (O(n .
حسب [[مبرهنة إيردوس-سيكريس]]، فإن أي متتالية من n+1 عدد صحيح مختلف إما أن يكون لها متتالية جزئية متزايدة أو متناقصة طولها n+1.
في القوائم التي تكون فيها كل تبديلات القائمة متماثلة تقريباً، يكون الطول المتوقع لأطول متتالية جزئية متزايدة هو تقريباً2√n.
عندما تسعى n إلى اللانهاية ، يكون طول أطول متتالية جزئية متزايدة في متتالية مبدّلة عشوائياً من n عنصر ذا توزّع يقترب من توزّع Tracy–Widom ، أي توزع أكبر قيمة ذاتية لمصفوفة عشوائية ضمن تجمع الغاوسي المتكامل .[[تصنيف:برمجة ديناميكية]]
[[تصنيف:توافقيات]]
[[تصنيف:خوارزميات]]
[[تصنيف:رياضيات]]
[[تصنيف:لغات شكلية]]