Recapitulare - Tehnici de programare

Exerciții de consolidare pentru Modulul 5: sume parțiale, two pointers, sliding window, șmenul lui Mars.

Exercițiul 1: Sume parțiale - suma pe interval

Avem un vector și trebuie să răspundem la întrebări: “care este suma elementelor de la poziția st la poziția dr?”. Completează formula care calculează suma pe interval folosind vectorul de sume parțiale sp.

Input:
8 2
3 1 4 1 5 9 2 6
3 6
1 8

Output:
19
31

Exercițiul 2: Two Pointers - pereche cu suma S

Avem un vector sortat și un număr S. Trebuie să găsim două elemente a căror sumă este exact S. Completează corpul buclei: ce facem când suma e prea mică? Dar când e prea mare?

Input:
7 10
1 3 4 5 7 9 11

Output:
1 9

Exercițiul 3: Sliding Window - suma maximă pe K elemente

Avem un vector și un număr K. Trebuie să găsim suma maximă a unei ferestre de exact K elemente consecutive. Completează linia care glisează fereastra: ce element adăugăm și ce element scoatem?

Input:
8 3
3 1 4 1 5 9 2 6

Output:
17

Exercițiul 4: Șmenul lui Mars - adunare pe interval

Primim operații de forma “adaugă val pe intervalul [st, dr]”. Completează cele două marcaje din vectorul de diferențe d.

Input:
8 2
2 5 3
4 7 2

Output:
0 3 3 5 5 2 2 0

Exercițiul 5: Cea mai lungă secvență crescătoare

Parcurgem vectorul și menținem lungimea secvenței crescătoare curente. Completează: ce condiție verificăm și cu ce resetăm contorul?

Input:
8
2 5 7 3 4 8 9 1

Output:
4