Problemet luktar dynamiskt på långt håll. Titta exempelvis på följande avsnitt med 5 tal:

2 * 3 + 4 * 7 * 6

Det finns fyra sätt att börja räkna ut avsnittet:
(2) * (3 + 4 * 7 * 6)
(2 * 3) + (4 * 7 * 6)
(2 * 3 + 4) * (7 * 6)
(2 * 3 + 4 * 7) * (6)

För att ta reda på det största resultat man kan få ut borde det räcka att veta det största värdet av delavsnitten och sedan bara välja det hopräkningssätt av de fyra möjliga som ger det största resultatet. Delavsnitten kan i sin tur räknas ut genom att kombinera ännu mindre avsnitt, o.s.v. Om man bygger upp det hela bakifrån, d.v.s. börjar med enstaka tal, sedan sätter ihop dem till avsnitt med 2 tal, 3 tal o.s.v., blir det enklast att skriva.

Men det finns en svårighet. Eftersom negativa tal kan finnas med är det inte säkert att det alltid är bäst att spara det största delresultatet. Om du tänker multiplicera med ett negativt tal är det ju bättre att du har t.ex. -40 än att ha 200. Som tur är går det att visa att det är tillräckligt att spara två summor varje gång, den största och den minsta. Det gör att man för varje beräkningssätt får 2*2 alternativa summor, och av alla de summor du får sparar du den största och den minsta.

Lägg märke till att om du skriver din lösning smart, behöver du inte bry dig om var du skär av polygonen. På slutet får du ett tal och ett räknesätt kvar och eftersom inte det räknesättet kommer att användas är det där du har skurit av den.

Tillbaka