The problem can be reduced to find largest sum in an array by scanning matrix in four directions: horizontal, vertical, two diagonal directions. We can extract the array, which we are working on, from the matrix and try to find the largest sum on that array using the following code:
// scan matrix in 4 directions:
// dir = {1:horizontal,2:vertical,3:left diagonal,4:right diagonal}
void solve(int dir)
{
for (int i=0; i<n; i++)
{
// if direction is vertical
int y=dir==2 ? 0 : i;
int x=dir==2 ? i : 0;
// extract the array in given direction
for (int j=0; j<n; j++)
{
array[j]=mat[y][x];
if (dir==1 || dir==3) x=(x+1)%n;
else if (dir==4) x=(x-1+n)%n;
if (dir>1) y=(y+1)%n;
}
scan();
special();
}
}
In this code, scan() searches the largest sum on the current array, and special() checks for the special case on the array. Now, we can work on the real problem: determining the largest sum. The straight-forward solution is to make an O(N^2) search on the array:
void scan()
{
for (int i=0; i<n; i++)
for (int j=i,sum=0; j<n; j++)
{
sum+=array[j];
if (maxsum<sum) maxsum=sum;
}
}
However, this solution requires O(N^3) time in total hence is an inefficient method. We can reduce the search on the array to O(N) as follows: while searching, if the current sum is less than or equal to 0, start searching the sum from next element in the array. The reason is, it is unnecessary to add new elements to a negative sum, starting from next element will be always greater. For example, consider the array {1,-9,9,-2}. In the first step the sum=1, in the second step sum=1+(-9)=-8 < 0. We can reset the sum and start from the next element 9 since 1+(-9)+9=1 is always less than or equal to 9. Here, the only twist is the cyclic search; we can check it by searching through the array at most twice.
void scan()
{
// circular scan
for (int i=0,x=0,sum=0; i<x+n; i++)
{
sum+=array[i%n];
if (maxsum<sum) maxsum=sum; // update maximal-sum in the sequence
// if current sum is less than 0,
// start a new sub sequence at the current location
if (sum<0)
if (i>=n) break; else sum=0,x=i+1;
}
}
Be careful that we have a special case in cyclic search. When the sum contains all the elements in the array with respect to the code above, we can solve the problem excluding the maximal negative-sum subsequence:
void special()
{
// find maximal negative-sum subsequence
int sum=0,neg=0;
for (int i=0; i<n; i++)
{
sum+=array[i];
if (neg>sum) neg=sum;
if (sum>0) sum=0;
}
// total sum of the array
sum=0;
for (int i=0; i<n; sum+=array[i++]);
if (sum!=neg) sum-=neg; // exclude maximal negative-sum subsequence
if (maxsum<sum) maxsum=sum;
}
Finally the complexity reduces to O(N^2) in total.
#include <fstream>
using namespace std;
#define MAX 800
#define MIN -1000000000
int n,mat[MAX][MAX],array[MAX],maxsum=MIN;
// read input
void fRead()
{
ifstream f("lepr.in");
f >> n;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) f >> mat[i][j];
f.close();
}
// write output
void fWrite()
{
ofstream f("lepr.out");
f << maxsum << "\n";
f.close();
}
// scan circular array for the maximal-sum subsequence
// scan the array once: O(n)
void scan()
{
int sum=MIN;
// circular scan
for (int i=0,x=0,t=0; i<x+n; i++)
{
t+=array[i%n];
if (sum<t) sum=t; // update maximal-sum in the sequence
// if current sum is less than 0,
// start a new sub sequence at the current location
if (t<0)
if (i>=n) break; else t=0,x=i+1;
}
if (maxsum<sum) maxsum=sum;
}
// special case: when all the numbers is in the sequence
// remove the maximal negative-sum subsequence from the array;
void special()
{
// find maximal negative-sum subsequence
int sum=0,neg=0;
for (int i=0; i<n; i++)
{
sum+=array[i];
if (neg>sum) neg=sum;
if (sum>0) sum=0;
}
// total sum of the array
sum=0;
for (int i=0; i<n; sum+=array[i++]);
if (sum!=neg) sum-=neg; // exclude maximal negative-sum subsequence
if (maxsum<sum) maxsum=sum;
}
// scan matrix in 4 directions:
// horizontal, vertical, left diagonal, right diagonal
void solve(int dir)
{
for (int i=0; i<n; i++)
{
int y=dir==2 ? 0 : i;
int x=dir==2 ? i : 0;
// extract the array in given direction
for (int j=0; j<n; j++)
{
array[j]=mat[y][x];
if (dir==1 || dir==3) x=(x+1)%n;
else if (dir==4) x=(x-1+n)%n;
if (dir>1) y=(y+1)%n;
}
scan();
special();
}
}
int main()
{
fRead();
for (int i=1; i<=4; solve(i++));
fWrite();
}