1. 
/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Dynamic Programming: Kadanes Algorithm
* Problem: 108 - MaximumSum
* Accepted: 0.500
* @author Evgeni Pavlidis
*
*/
import java.util.*;
import java.io.*;

class Main {

public static void main(String...args)
{
Scanner scanner = new Scanner(System.in);
int n, max = Integer.MIN_VALUE, sum, current;

n = scanner.nextInt();
int[][] m = new int[n][n];
int[][] columnSum = new int[n][n];


for(int y=0; y < n; y++)
for(int x=0; x < n; x++)
m[y][x] = scanner.nextInt();

// calc the column sum for every y
for(int x=0; x < n; x++)
{
sum = 0;
for(int y=0; y < n; y++)
columnSum[y][x] = sum = sum + m[y][x];
}

//System.out.println(Arrays.deepToString(columnSum).replace("],","\n"));

// go through all row combinations and accumulate sum
for(int rowStart=0; rowStart < n; rowStart++)
for(int rowEnd=rowStart; rowEnd < n; rowEnd++)
{
current = 0;
for(int column=0; column < n; column++)
{
current+= columnSum[rowEnd][column]-columnSum[rowStart][column];
if(current > max)
max = current;

if(current < 0)
current = 0;
}
}

System.out.println(max);
}
}