partitura

Algoritmul, pas cu pas

Gândește-te la fiecare grup ca la o „găleată" în care punem înălțimi, iar scorul găleții e suma la pătrat. Suma totală a înălțimilor e fixată din start — n-o putem schimba, indiferent cum grupăm. Ce putem alege e cum o împărțim între găleți. Și aici e tot trucul: pentru o sumă fixă, suma de pătrate crește cu cât valorile sunt mai inegale ($3^2 + 1^2 = 10$ bate $2^2 + 2^2 = 8$). Așadar vrem înălțimile mari strânse la un loc, nu împrăștiate.