یک جایگشت از اعداد ۱ تا $n$ داریم و یک برنامه برای پیدا کردن بیش‌ترین عدد. برنامه به صورت دنباله‌ای از جملات $swap(i,j)$ با شرط $i<j$ می‌باشد. یک دستور به شکل $swap(i,j)$ بدین معنی است که اگر عدد $i$ ام از عدد $j$ ام کوچک‌تر است جای آن‌ دو را عوض می‌کند. یک برنامه‌ی بیشینه‌یابی باید در انتها بیش‌ترین عدد را در خانه‌ی اول قرار دهد.

یک برنامه‌ی بیشینه‌یابی مورد اطمینان است اگر با حذف کردن حداکثر یک دستور از برنامه نیز به درستی عمل کند. یک برنامه به شما داده می‌شود. حداقل تعداد دستور را به آخر آن اضافه کنید تا یک برنامه‌ی بیشینه‌یابی مورد اطمینان شود. برای این کار الگوریتمی از مرتبه‌ی $O(n+x)$ ارائه کنید اگر برنامه‌ی اولیه شامل $x$ دستور باشد.

• سوال بعد
• سوال قبل