I was little discouraged when my O(n^4) solution got AC.What remains the purpose of Dp ,if I could do it by complete search.

Please mail me the O(n^3),O(n^2),O(n) solution for this task,any or all complexity written here.
My mail id is royalbird.raman@gmail.com
thanks for your support

O(n) cannot be achieved in this problem, because of O(n^2) input.

I think you use a kind of DP when you sum the numbers in every rectangle.
(In fact, the most complete search has the complexity O(n^6)) =))