I was asked this question during an interview of a startup comany.
The question was, given a matrix of integers, could be both positive and negative, give the max path sum in the matrix that starts and ends at any node.

I first proposed a brute force DFS solution, with some pruning that a starting point must be a positive cell.
Then I came up with a DP idea, sort all the elements first, then start with the smallest and keep a set of visited elements, record the max path sum that ends at each element.

But the interviewer seemed confused. He then asked me to implement the brute force solution. I did and ran through a few small testcases. Seems he's not very satisfied with the solution either. What could be wrong? Is there any better solution?