algoritmiada-2009/runda-finala/solutii/trmax

Trmax

h1. 'Trmax':problema/trmax

h2(#trmax). 'Trmax':problema/trmax
 
Problema se rezolva cu ajutorul programarii dinamice. Pentru inceput vom calcula matricea $A$, unde $A[i][j]$ reprezinta numarul de $0$-uri consecutive avand pe ultima pozitie elementul de pe pozitia $(i, j)$, in cazul in care acesta este nenul, sau $0$ altfel. Relatia de recurenta este evidenta, $A[i][j] = A[i][j-1] + 1$, daca elementul este nul, $A[i][j] = 0$ , altfel.
 
Apoi se calculeaza matricea $bst$, in $bst[i][j]$ se va memora inaltimea celui mai mare triunghi care are in coltul din dreapta jos elementul de pe pozitia $(i, j)$. Relatia de recurenta este $bst[i][j] = min(bst[i-1][j-1] + 1, (A[i][j] + 1) /2)$. Raspunsul final va fi maximul din aceasta matrice ridicat la patrat.