Să considerăm următoarea problema:

h3(#problema-1). Problema 1: 'Drilling':http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en

h3(#problema-1). Problema 1: 'Drilling':http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en (Algorithmic Engagements 2009, Round 3)

bq. Se da un şir de $N$ numere naturale $(a{~1~}, a{~2~}, ..., a{~N~})$. Se ştie că un prefix al acestui şir (adică o subsecvenţă de la începutul şirului, posibil nulă) este **defect**. Toate elementele din acel prefix (şi doar din acel prefix) sunt defecte. Se ştie de asemenea că se poate testa orice poziţie $i$ în timp $a{~i~}$ pentru a afla dacă este defectă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este defect.