1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 108 Maximum Sum
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
*
* @author Burgmair Stefan
* @author YYY
* @version 1.0, 10/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.544
*/



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());

int[] input = new int[n*n];
int inputIndex = 0;
do
{
String[] arr = reader.readLine().split(" ");
for (int i = 0; i < arr.length; i++)
{
if (!arr[i].equals(""))
{
input[inputIndex] = Integer.parseInt(arr[i]);
inputIndex ++;
}
}
}while(reader.ready());


int [][] map = new int [n][n];
inputIndex = 0;
for (int i = 0; i < n; i++)
{
for (int o = 0; o < n; o++)
{
map[i][o] = input[inputIndex];
inputIndex ++;
}
}

// System.out.println();
// for (int i = 0; i < n; i++)
// {System.out.println();
// for (int o = 0; o < n; o++)
// {
// System.out.print(map[i][o] + " ");
// }
// }
// System.out.println();

int maximumSum = map[0][0];

// corner in left top of the rectangle
for (int i = 0; i < n; i++)
{
for (int o = 0; o < n; o++)
{
int [][] proxyMap = new int [n][n];
// corner in right bottom of the rectangle
for (int a = i; a < n; a++)
{
for (int b = o; b < n; b++)
{
int proxySum = 0;
if(a != 0)
proxySum = proxyMap[a - 1][b];
for (int d = o; d <= b; d ++)
{
proxySum = proxySum + map[a][d];
}
proxyMap[a][b] = proxySum;
}
}
for (int x = i; x < n; x ++)
{//System.out.println();
for (int y = o; y < n; y ++)
{//System.out.print(proxyMap[x][y] + " ");
if (proxyMap[x][y] > maximumSum)
{
maximumSum = proxyMap[x][y];
}
}
} //System.out.println();
}
}

System.out.println(maximumSum);

}
}

---------------------------------------------------------------------------
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);
}
}