0181 - SecvCresc

Sursa: 0181 - SecvCresc

---

Cerinţa

Se dau n numere naturale, reprezentând elementele unui vector. Determinați cea mai lungă secvență de elemente ordonate strict crescător din vector. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga.

Date de intrare

Fișierul de intrare secvcresc.in conține numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fișier pot fi dispuse pe mai multe linii.

Date de ieșire

Fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de sfârșit ai secvenței determinate.

Restricţii şi precizări

• 0 < n ≤ 10.000
• elementele vectorului vor fi mai mici decât 1.000.000 și sunt numerotate de la 1

Exemplu

Intrare

9

2 6 4 5 8 9 6 3 4

Ieșire

3 6

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0181 - SecvCresc

def citire():

   with open("secvcresc.in", "r") as f:
       n = int(f.readline())
       v = []
       for line in f:
           v += list(map(int, line.split()))
   return n, v

def rezolvare(n, v):

   max_length = 1
   max_start = max_end = start = end = 0
   length = 1
   for i in range(1, n):
       if v[i] > v[i - 1]:
           length += 1
           end = i
       else:
           if length > max_length:
               max_length = length
               max_start, max_end = start, end
           length = 1
           start = end = i
   if length > max_length:
       max_length = length
       max_start, max_end = start, end
   return max_start + 1, max_end + 1

def validare(n, v, start, end):

   for i in range(start - 1, end - 1):
       if v[i] >= v[i + 1]:
           return False
   return True

if __name__ == "__main__":

   n, v = citire()
   start, end = rezolvare(n, v)
   with open("secvcresc.out", "w") as f:
       f.write(f"{start} {end}\n")
   if validare(n, v, start, end):
       print("Rezultat corect!")
   else:
       print("Rezultat incorect!")

</syntaxhighlight>

Explicatie Rezolvare

Pentru a rezolva această problemă, putem parcurge vectorul și ține în variabila lungime lungimea secvenței curente. De asemenea, putem ține și variabilele start și end care reprezintă indicele de început și sfârșit al secvenței curente. Dacă găsim o valoare mai mare decât precedenta, atunci lungimea secvenței crește și actualizăm end cu indicele curent. Dacă găsim o valoare mai mică sau egală cu precedenta, atunci secvența curentă se termină și verificăm dacă este mai lungă decât cea maximă găsită până acum. Dacă da, actualizăm variabilele max_start, max_end și max_length