Encontre a subsequência com a maior soma de elementos em uma matriz

Eu recentemente entrevistei uma empresa e eles me pediram para escrever um algoritmo que encontre a subsequência com a maior soma de elementos em uma matriz. Os elementos na matriz podem ser negativos. Existe uma solução O (n) para isso? Quaisquer boas soluções são muito apreciadas.