ID #123 · Colecția InfoAs · Operatori și expresii

Problema Subsir zig zag

Numim un șir _zig-zag_ o secvență de numere `(z<sub>1</sub>, z<sub>2</sub>, z<sub>3</sub>, …, z<sub>k</sub>)` cu proprietatea că `z<sub>1</sub> < z<sub>2</sub> > z<sub>3</sub> < … z<sub>k</sub>` sau `z<sub>1</sub> > z<sub>2</sub> < z<sub>3</sub> > … z<sub>k</sub>`. ## Cerință Se dă un șir de `n` numere naturale. Să se determine lungimea celui mai lung subșir zig-zag al șirului inițial. ## Date de intrare Programul citește de la tastatură, de pe prima linie, numărul natural `n`, iar de pe a doua linie, cele `n` numere naturale ale șirului, separate prin câte un spațiu. ## Date de ieșire Programul afișează pe ecran lungimea subșirului zig-zag de lungime maximă al șirului inițial. ## Restricții și precizări * `1 ≤ n ≤ 1000` * `1 ≤ elementele șirului ≤ 2.000.000.000`