Yechim tahlili

Energiya minorasi

Muallif: __thecrash__

Massivni chapdan o'ngga bir marta yurib chiqamiz va ikkita o'zgaruvchi saqlaymiz:

  • \(cur\) — hozirgi o'suvchi zanjirning uzunligi.
  • \(best \) — hozirgacha topilgan eng uzun zanjirning uzunligi.

Har bir \(i\) pozitsiyasida:

  • Agar \(a_i > a_{i-1}\) bo'lsa — zanjir davom etyapti, \(cur\) ni \(1\) ga oshiramiz.
  • Aks holda (\(a_i \le a_{i-1}\)) — zanjir uzildi, \(cur\) ni qaytadan \(1\) ga tenglashtiramiz (yangi zanjir joriy elementdan boshlanadi).

Har bir qadamda \(best = max(best, cur)\) bilan javobni yangilab boramiz.

Navbatdagi musobaqa