Solução por Sofhia de Souza
Esse problema é facilmente resolvido com um algoritmo guloso. A ideia é a seguinte: sabemos que, para formarmos um triângulo, suas extremidades têm que começar com altura 1 e ir crescendo de 1 em 1, certo? Usaremos então esse conceito ao nosso favor, para que possamos limitar as alturas que cada coluna pode usar em um triângulo. Primeiro, limitaremos a extremidade esquerda do muro: colocaremos a primeira como 1, a segunda como 2, e assim por diante (enquanto as alturas dessas colunas permitirem). Se a altura que queremos (a altura anterior + 1) for maior que a altura da coluna, colocamos a própria altura da coluna e continuamos normalmente com o algoritmo. Depois, com esse vetor atualizado, faremos a mesma coisa com a extremidade direita.
Simulemos isso com o seguinte exemplo : 5 4 9 3 2. Sabemos que a primeira coluna pode ter altura no máximo 1, pois não possui mais nenhuma coluna pra esquerda, certo? Logo, agora nosso vetor é 1 4 9 3 2. Agora, a segunda coluna, ela pode ser no máximo 2, pois sua coluna anterior é no máximo 1. Então, nosso vetor agora se torna 1 2 9 3 2. Faremos o mesmo para as últimas 3 colunas, e terminaremos com o vetor igual a 1 2 3 3 2. Agora, aplicaremos o mesmo algoritmo, de trás pra frente no vetor. Temos que a coluna 5 pode ser no máximo 1, pois não possui mais nenhuma coluna a sua direita. Ficamos então com o vetor 1 2 3 3 1. A quarta coluna pode ser no máximo 2, pois a coluna a sua direita pode ser no máximo 1. Ficamos com 1 2 3 2 1. Fazemos a mesma coisa com as 3 colunas que faltam, e terminamos com o vetor 1 2 3 2 1. Assim, a resposta será a maior altura que aparece no vetor, nesse caso, 3.
Segue o código para melhor entendimento:
https://gist.github.com/sofhiasouza/c5bfb76e9d3613391229e913adcf9c92