یک دنباله از اعداد متفاوت تناوبی است اگر و فقط نسبت (بزرگی یا کوچکی) هر عدد با دو عدد کناری‌اش (در صورت وجود) متفاوت باشد. به‌عبارت دیگر هر یک از اعداد این دنباله (به‌جز اوّلی و آخری) دقیقاً از یکی از دو عدد کناری‌اش کوچک‌تر و از دیگری بزرگ‌تر باشد.

یک دنباله از ‎$n$‎ عدد متفاوت داده شده است. می‌خواهیم بزرگترین زیردنباله‌یِ (نه لزوماً متوالی) از اعضای این دنباله را پیدا کنیم به طوری که اعداد این زیردنباله، یک دنباله‌ی تناوبی را تشکیل دهند. مثلاً یکی از بزرگترین زیردنباله‌های تناوبی دنباله‌ی ‎$3,4,10,20,1,-2,5,0,11$‎ زیردنباله‌ی ‎$3,4,-2,5,0,11$‎ است. الگوریتمی با زمان اجرای متوسّط ‎${\cal O}(n\lg n)$‎ برای پیداکردن بزرگ‌ترین زیردنباله تناوبی روی یک دنباله ارائه کنید.

زمان اجرای یک الگوریتم برای چنین کاری ‎«به‌طور متوسّط»‎ از ‎${\cal O}(n\lg n)$‎ است، اگر و فقط اگر جمع زمان اجراهای این الگوریتم روی همه‌ی ‎$n!$‎ جایگشتِ ‎$n$‎ عدد متفاوت (به‌عنوان ورودی الگوریتم) از ‎${\cal O}(n! \times n\lg n)$‎ باشد.

• سوال قبل