De ce contează?
Mergi pe munte și, la fiecare bornă, vrei să știi care a fost cel mai înalt punct prin care ai trecut până acolo. Nu te întorci de fiecare dată să recitești toate bornele de dinainte — ții minte un singur număr: „cel mai înalt de până acum”. Când ajungi la o bornă nouă, o compari doar cu acel număr și, dacă e mai înaltă, îl actualizezi. Exact asta înseamnă maximul pe prefixe: pentru fiecare poziție, cel mai bun lucru văzut de la început până acolo.
Intuiția
Ai un șir a și vrei, pentru fiecare poziție i, cel mai mare element dintre a[0], a[1], …, a[i] — adică maximul prefixului care se termină la i. Îl notezi pre[i]. Imaginea mentală: parcurgi șirul o singură dată, ducând cu tine „recordul de până acum”. La fiecare pas îl compari cu elementul curent și, dacă e nevoie, îl ridici. Maximul pe prefixe e tabelul tuturor acestor recorduri.