[Vincenzo1968]

E ci metto pure il carrico da undici:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
	int **m;
	int side;
} Array;

typedef struct tagResult
{
	int row1;
	int col1;
	int row2;
	int col2;
	int sum;
} Result;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	pArray->side = GetArraySize(szFileName);
	if ( pArray->side <= 0 )
	{
		printf("Errore nella lettura del file.\n");
		return S_ERROR;
	}

	pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( pArray->m != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( pArray->m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= pArray->side)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' || c == '\r' || c == '\n' )
			{
				pArray->m[riga + 1][colonna + 1] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int FindKadaneSubCubic(Array *pArray, Result *pRes)
{
	int Somma;
	int i, j, k, l, m, n, kmin, x, z, x1, x2, y1, y2, s, t;
	int min_prefix;

	int **sum;
	int **column;

	column = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( column != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( column[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	sum = (int**)calloc(pArray->side + 1, sizeof(int*));
	if ( sum != NULL )
	{
		for ( x = 0; x < pArray->side + 1; x++ )
		{
			sum[x] = (int*)calloc(pArray->side + 1, sizeof(int));
			if ( sum[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	m = pArray->side;
	n = pArray->side;

	for( i = 1; i <= m; i++ )
	{
		for( j = 1; j <= n; j++ )
		{
			column[i][j] = column[i - 1][j] + pArray->m[i][j];
			sum[i][j] = sum[i][j - 1] + column[i][j];
		}
	}

	x1 = 0; x2 = 0; y1 = 0; y2 = 0;
	Somma = -999999999;

	for( z = 1; z <= m; z++ )
	{
		for( i = 1; i <= n; i++)
			column[z - 1][i] = 0;

		for( x = z; x <= m; x++)
		{
			t = 0;
			s = -999999999;
			k = 0;
			l = 0;
			kmin = 0;
			min_prefix = 0;

			for( i = 1; i <= n; i++ )
			{
				t = sum[x][i] - sum[z - 1][i] - min_prefix;
				if( t > s )
				{
					s = t;
					k = kmin;
					l = i;
				}

				if( sum[x][i] - sum[z - 1][i] < min_prefix )
				{
					min_prefix = sum[x][i] - sum[z - 1][i];
					kmin = i;
				}
			}

			if( s > Somma )
			{
				Somma = s;
				x1 = x;
				y1 = l;
				x2 = z;
				y2 = k + 1;
			}
		}
	}

	for ( x = 0; x < pArray->side + 1; x++ )
		free(column[x]);
	free(column);

	for ( x = 0; x < pArray->side + 1; x++ )
		free(sum[x]);
	free(sum);

	pRes->row1 = x2 - 1;
	pRes->col1 = y2 - 1;
	pRes->row2 = x1 - 1;
	pRes->col2 = y1 - 1;
	pRes->sum = Somma;

	return 0;
}

int main()
{
	clock_t c_start, c_end;
	Array a;
	Result res;
	Stati stato;
	int x;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

	c_start = clock();
	stato = DFA(szFileName, &a);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}
	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	FindKadaneSubCubic(&a, &res);
	c_end = clock();
	printf("\nRiga1       -> %d\nColonna1    -> %d\n\nRiga2       -> %d\nColonna2    -> %d\n\nSomma       -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
	printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	for ( x = 0; x < a.side + 1; x++ )
		free(a.m[x]);
	free(a.m);

	return 0;
}

Grazie all'algoritmo ideato dai Sigg. Tamaki e Tokuyama, la complessità scende al di sotto di O(m^2 * n) e, quindi, nel caso m = n, sotto O(n^3).