Solução Informática Intermediário – Semana 45

Solução de Frederico Bulhões

Para resolver esse problema devemos usar soma de colunas e linhas para encontrar a melhor posição rapidamente. Primeiramente vamos ler a matriz $$m[i][j]$$, onde a posição $$(i,j)$$, indica o $$X_{i,j}$$. Além disso vamos cirar dois vetors, $$linha[i]$$ e $$coluna[j]$$, onde $$linha[i]$$, indica a soma de todos os $$X_{ij}$$ na linha $$i$$, e $$coluna[j]$$, indica a soma das $$X_{ij}$$ na coluna $$j$$. Agora podemos passar por todas as posições  $$(i,j)$$, e ver o máximo de $$coluna[i]+linha[j]-2\cdot m[i][j]$$, subtraindo $$m[i][j]$$ duas vezes pois está sendo contado duas vezes a mais.

Assim achando o máximo dessa expressão para todo $$(i,j)$$, temos a resposta da questão.

Código para melhor entendimento:

https://gist.github.com/fredbr/55d967bb414af8c7a89258403be9b663