I recently participated in Google's Online Coding Challenge. Following is one of the 2 questions given to me. I couldn't solve it during the contest. After the contest, I looked up the internet for the same but to no avail. Question goes as follows,

Problem:

You are given a $$$N*M$$$ matrix where each cell has a positive number, $$$A_{ij}$$$, written on it. You need to start from first column and end at last column such that the cost of the path taken is minimum possible. We define cost of the path as difference between maximum and minimum value among all values lying on the chosen path.

In one move you can go to any row of $$$(j+1)^{th}$$$ column from $$$j^{th}$$$ column. You can start from any row of first column and end up on any row of last column. Find the minimum possible cost.

Constraints:

$$$1\leq N,M\leq 500$$$
$$$1\leq A_{ij}\leq 10^9$$$

I was thinking some modification of some standard DP would do but couldn't come up with one.
Any help will be appreciated. Thanks!