Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
Prova a disegnare su un foglio di carta l'asse delle ascisse di un piano cartesiano. In parole povere è una semplice linea orizzontale in cui:
Una volta disegnato ciò, metti la penna sul punto 0 e comincia a scansionare l'array di numeri che ti vengono dati in input: quando incontri un +1 muoviti verso destra, e analogamente muoviti verso sinistra quando incontri un -1.
Per esempio con il primo input fornito dal testo, -1 -1 -1, raggiungerai il punto -3 dell'asse, e la risposta per quell'input è 3. Con l'ultimo input, -1 +1 +1 +1 -1 +1 +1 +1 -1 +1, raggiungerai invece il punto 4... ma la risposta per quell'input è 5 🤔
Guardando l'asse disegnato sul foglio puoi osservare che per quel caso di input la superficie totale percorsa dalla penna è proprio uguale a 5. Con un po' di ragionamento possiamo convincerci che la risposta alla domanda del problema (ovvero: quanti studenti diversi al minimo sono stati nella stanza) è equivalente a calcolare tale superficie, o più semplicemente: la differenza tra il "massimo punto" ed il "minimo punto" raggiunti dalla penna.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int minimo = 0, massimo = 0, somma = 0, N;
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
somma += x;
minimo = min(minimo, somma);
massimo = max(massimo, somma);
}
cout << "Case #" << t << ": " << massimo - minimo << endl;
}
}