== include(page="template/taskheader" task_id="collar") ==

Tassadar a descoperit un colier Xel’Naga format din $N$ perle, fiecare perlă $i$ având asociat un coeficient $V{~i~}$, iar frumuseţea colierului este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. Tassadar vrea să împartă colierul în mai multe coliere de lungimi egale, astfel încat fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial, fiecare perlă din colierul iniţial să facă parte din exact un colier nou, iar suma frumuseţilor colierelor noi să fie maximă.

Tassadar a descoperit un colier Xel’Naga format din $N$ perle, fiecare perlă $i$ având asociat un coeficient $V{~i~}$, iar frumuseţea colierului este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. El vrea să împartă colierul în mai multe coliere de lungimi egale, astfel încat fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial, fiecare perlă din colierul iniţial să facă parte din exact un colier nou, iar suma frumuseţilor colierelor noi să fie maximă.

Tassadar nu este un bijutier prea iscusit şi vă roagă pe voi să-i spuneţi care este suma frumuseţilor maximă pe care o poate obţine printr-o împărţire a colierului.