First, using a matrix to store the value of a[i][j] is unnecessary,if a
array s[] is used to store the summation of first i elements of A[],
that is s[i] = A[1] + ... +A[i], which means a[i][j] = s[j] - s[i - 1].
Second, computing "max" costs O(n) by using s[], The problem becomes to
find a interval which achieves the max value, that is to find a proper
upper bond i and a lower bond j. The most tricky thing which leads the
algorithm to O(n) is when you scan each i j from 1 to n, you never
return.
hope it helps :)
