Thought Process

Generating the matrix is simple, then we just have to find the maximum-sum subsequence of every row, column, diagonal, and anti-diagonal and return the maximum, so the crux of this problem is how to find the maximum-sum subsequence, which luckily for me I had as a homework problem during a university class!

The problem is commonly known as Maximum subarray problem and can be solved in O(n) time.