108 - Maximum Sum

[Fauhat(AUST)]

Dear all,

I was facing this problem many days ago. I was getting presentation error in 108 (Maximum Sum). I was printing the output without any space and new line.
I also got a reply stating
"not including space is ok, but why don't you print new lines. In every problem, there is at least one new line after every case of output".

I am very happy to get the reply. But from the very begiening I too know that in every problem there should be a new line after every case of output. This is
indeed very true if there are many cases of output. But what if there should be only one case of input and output.
Let's have a look to the input and the output of this problem.


Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

Sample Output

15



The question is whether there should be provition of taking inputs before end of file i.e. there will be many cases of input or there will be only one case of input. if there is only one case of input then there will be only one case of output and how to print that output. I printed the output straight forward without space and new lines considering there will be just one case of input and output. Considering just one case of input and output I also tried with new lines and space later if I am not wrong. Well, it is more acceptable that there will be only one case of input as the problem states :


"Input and Output
The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127].


The output is the sum of the maximal sub-rectangle"


"The input consists of an array of integers" by this statement I think there should be only one array i.e. only one case of input.

Moreover, I just got presentation error instead of Wrong Answer. And if there is only one case of input, naturally there will be only one output for the input which I printed straight. My question is why I got presentation error in this problem. Can there be any other form of printing the output if there should be only
one output.

I am trying to solve this problem again after a long time. So,if anyone has knowledge about this please help.

Regards,
Fauhat

[Fauhat(AUST)]

Dear All,
In my previous post I already mentioned that I was facing trouble with problem 108 (Maximum Sum). A long time ago I was getting presentation error in
this problem. To know detail about this please read my previous post "presentation error in Maximum Sum-108". Now, after quite a long time I intended to
solve the problem again. I just submiited the previous code out of Inquisitiveness. But this time it is not presentation error I got. If I am not wrong I got Wrong Answer with the same code I got presentation error.

Please help.

[sohel]

Perhaps it'd have been a better idea if you had made your query in the other post so that everyone can view the code and make comments.

[shafin5]

/*What is the problem in this solution of problem 108......plz help...*/


#include<stdio.h>
int i,j,p,q,n,ar[101][101],ar1[101][101];
int sum,max=-999999999;

int main ()
{
int s;
while(scanf("%d",&n) != EOF){

for(i=0;i<n;i++)
{
s=0;
for(j=0;j<n;j++)
{
scanf("%d",&ar[j]);
}
}
sum=0;
for(i=0;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
sum=0;
for(i=1;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
ar1[j]=ar[j]+ar1[j-1]-ar1[i-1][j-1]+ar1[i-1][j]-ar1[i-1][j-1]+ar1[i-1][j-1];
}
}

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(p=i;p<n;p++)
{
for(q=j;q<n;q++)
{
sum=0;
if (i >0 && j> 0)
sum=ar1[p][q]-ar1[i-1][q]-ar1[p][j-1]+ar1[i-1][j-1];
else
{
if(i==0 && j==0)
sum=ar1[p][q];
if(i==0 && j !=0)
{
sum=ar1[p][q]-ar1[p][j-1];
}
if(j==0 && i != 0)
{
sum=ar1[p][q]-ar1[i-1][q];
}
}
if(sum>max)
{
max=sum;
}
}
}
}
}

printf("%d",max);
}
return 0;
}

[Javo]

Hi everybody!

I tried out with this not more efficient algorithm [ O(n^4) ],perhaps can run on time, but I got WA!, someone could give me a hand?

Code: Select all

done!

Thanks in advance for your answers!

[mf]

cout<<FindMax();

You should terminate the output line with a newline character ("\n" or std::endl)

long maxSum=-1270000,sum;

You can use LONG_MIN constant defined in limits.h to initialize a variable with the most negative value representable by a 'long' type.

[Javo]

Thanks my friend! I should be more concentrated!

[camilop25]

Hi to everybody, I did the following code for the problem 108:

Code: Select all

#include <iostream>

using namespace std;

int datos[100][100],cantidadLados,maximoActual;

struct Precalculo
{
    int valor;
    int x1;
    int y1;
    int x2;
    int y2;
    Precalculo *siguiente;
};

Precalculo *cabeza;

void agregarPrecalculo(Precalculo*);
bool hallarValorPrecalculado(Precalculo*,int&);
void liberarMemoria();
int hallarMaximo(int,int,int,int);

int main()
{
    int maximo,sumatoria,cantidadElementosMatriz,x,y,i,nuevoDato;
    bool soloPositivos,soloNegativos;
      
    while(cin>>cantidadLados)
    {
        x=y=sumatoria=0;
        soloNegativos=soloPositivos=true;
        
        cantidadElementosMatriz = cantidadLados*cantidadLados;
        
        for (i=0;i<cantidadElementosMatriz;i++)
        {
            cin>>nuevoDato;
            
            datos[y][x] = nuevoDato;
            x++;
            if (x >= cantidadLados)
            {
                x=0;
                y++;
            }
            
            if (i==0) maximo = maximoActual = datos[0][0];
            
            if (nuevoDato > 0)
            {
                soloNegativos=false;
                sumatoria+=nuevoDato;
            }
            else if (nuevoDato <= 0)
            {
                if (nuevoDato < 0)
                    soloPositivos = false;
                
                if (nuevoDato > maximo) maximo = nuevoDato;
            }
        }
        
        if (soloPositivos)
            cout <<sumatoria<<endl;
        else if (soloNegativos)
            cout <<maximo<<endl;
        else 
        {
            cout <<hallarMaximo(0,0,0,0)<<endl;
            liberarMemoria();
        }
    }
    return EXIT_SUCCESS;
}

void agregarPrecalculo(Precalculo *nuevoPrecalculo)
{
    nuevoPrecalculo->siguiente = cabeza;
    cabeza = nuevoPrecalculo;
}

bool hallarValorPrecalculado(Precalculo *referenciaPrecalculo, int &respuesta)
{
    bool valorDevuelto = false;
    
    Precalculo *nodoActual = cabeza;
    
    while (nodoActual!=NULL)
    {
        if (referenciaPrecalculo->x1 == nodoActual->x1 &&
            referenciaPrecalculo->y1 == nodoActual->y1 &&
            referenciaPrecalculo->x2 == nodoActual->x2 &&
            referenciaPrecalculo->y2 == nodoActual->y2)
        {
            respuesta = nodoActual->valor;
            valorDevuelto = true;
            
            break;
        }
        
        nodoActual=nodoActual->siguiente;
    }
    
    return valorDevuelto;
}

void liberarMemoria()
{
    Precalculo *nodoActual = cabeza, *nodoSiguiente;
    
    while (nodoActual != NULL)
    {
        nodoSiguiente = nodoActual->siguiente;
        
        delete nodoActual;
        
        nodoActual = nodoSiguiente;
    }
    
    cabeza = NULL;
}

int hallarMaximo(int x1,int y1,int x2,int y2)
{
    if (x1 >= cantidadLados || x2 >= cantidadLados || y1 >= cantidadLados || y2 >= cantidadLados) return datos[0][0];
    
    int valorPrecalculado, &referenciaValorPrecalculado = valorPrecalculado, 
        sumatoriaSubMatriz = 0, 
        x,y,
        conDer,conAba,soloDer,soloAba,conAmbos;
        ;
    
    Precalculo *precalculoReferencia = new Precalculo;
    precalculoReferencia->x1 = x1;
    precalculoReferencia->y1 = y1;
    precalculoReferencia->x2 = x2;
    precalculoReferencia->y2 = y2;
    
    
    if (hallarValorPrecalculado(precalculoReferencia,referenciaValorPrecalculado))
    {
        delete precalculoReferencia;
        return valorPrecalculado;
    }
    
    
    for (y=y1;y<=y2;y++) for (x=x1;x<=x2;x++) sumatoriaSubMatriz += datos[y][x];
    
    if (sumatoriaSubMatriz > maximoActual) maximoActual = sumatoriaSubMatriz;
    
    conDer = hallarMaximo(x1,y1,x2+1,y2);
    conAba = hallarMaximo(x1,y1,x2,y2+1);
    soloDer = hallarMaximo(x1+1,y1,x2+1,y2);
    soloAba = hallarMaximo(x1,y1+1,x2,y2+1);
    conAmbos = hallarMaximo(x1,y1,x2+1,y2+1);
    
    if (conDer > maximoActual) maximoActual = conDer;
    if (conAba > maximoActual) maximoActual = conAba;
    if (soloDer > maximoActual) maximoActual = soloDer;
    if (soloAba > maximoActual) maximoActual = soloAba;
    if (conAmbos > maximoActual) maximoActual = conAmbos;

    precalculoReferencia->valor = maximoActual;
    agregarPrecalculo(precalculoReferencia);
    
    return maximoActual;
}

I tried it with my computer and takes about a half o second solving a 15x15 matrix, however the judge says that it's too slow, I want to know if my code is really slow, or it is waiting a inputcode when the judge is waiting an answer. I also want to know the sample size used by the judge, and the resources the judge has to run the programs.

Thank you.

[mf]

I tried it with my computer and takes about a half o second solving a 15x15 matrix

You should try a 100x100 matrix. The input description clearly says "N may be as large as 100", so it's very likely that it's about that big in the judge's test.

[camilop25]

I tried it with my computer and takes about a half o second solving a 15x15 matrix

You should try a 100x100 matrix. The input description clearly says "N may be as large as 100", so it's very likely that it's about that big in the judge's test.

I solved several problems in the uva, and many times it says the maximiun value, but it's clear that this value is not tried by the judge due to the excesive processing effort, read the problem and note that a 15x15 matrix requires a lot of processing, at least two million of comparisons, because the program has to compare each submatrix in a whole matrix, and select the biggest sum.

An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.

[mf]

Your algorithm is very inefficient, that's why it takes so long even on small matrices. I think it's complexity is about O(n^8)!

There's a very straightforward O(n^4) solution, and it's good enough to get accepted.
And then there's an even better O(n^3) algorithm.

An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.

My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.

[camilop25]

Your algorithm is very inefficient, that's why it takes so long even on small matrices. I think it's complexity is about O(n^8)!

There's a very straightforward O(n^4) solution, and it's good enough to get accepted.
And then there's an even better O(n^3) algorithm.

An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.

My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.

When you use dynamic programming, the order is less important, because the storage of pre-calculated data helps to avoid repeated calculations, for that I use a linked list, I also tried it but avoiding consulting the linked list, the program takes several minutes and about 500 mbytes of ram, for the same matrix consulting the linked list, the answer is instant, for that reason sometimes orders about a O(n^n) is more efficient than a O(n) if the first one saves the calculated data (that is repeated several times) and then just visit them.

For the above reason, I thought some people will advise me to improve the precalculate data system, such as implementing an AVL tree or something like that, if you know a better algorithm of a lower order, please say how it is.

[mf]

You don't need dynamic programming in this problem. Brute force works very well here, and needs very little memory.

But speaking of DP, you should never use linked list for memo tables in DP. Use hash tables, binary search trees (such as STL's std::map), or simple arrays if possible. Linked list with m elements needs O(m) time to search for an element, but arrays, hash tables and BSTs do it a lot faster - in O(1) and O(log m) time.
For example, your algorithm's complexity is O(n^8) because you have O(n^4) states in your DP, and for each state you do an O(n^4) search in linked list and O(1) additional work to compute answer. If you replace linked list with std::map, its complexity would drop to O(n^4 log n). That's already quite fast, but probably wouldn't get accepted because of its huge memory requirements.

I also tried it but avoiding consulting the linked list, the program takes several minutes and about 500 mbytes of ram, for the same matrix consulting the linked list, the answer is instant,

Without memoization your program's complexity is exponential (I think it's Omega(5^n) or something like that, because you have 5 recursive calls), but once you added memoization (with a linked list), it became polynomial - of order O(n^8). See? Now, how can you claim such things:

sometimes orders about a O(n^n) is more efficient than a O(n)

That's simply now true (not for any large enough n, at least), and you've already observed that - an exponential-time algorithm took minutes, but a polynomial-time algorithm takes only an instant...

[anjanpstu]

I faced problem when I started this .But now I got accepted .
there is no need to use EOF and at last print only one '\n' and the output for all negetive numbers will be the lowest negetive number
i.e for
2
-1 -2
-3 -4
my accepted code give [-1]
and for
3
-12 -13 -4
-2 -3 -5 -6 -4 -6
gives -2

[aaa111]

Hi,
This is my code. I tried the test cases from the algorithmist site which seems to give me correct answer.But i am getting WA after submission:

Code: Select all

#include<iostream>

using namespace std;

void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size);

int main(void)
{
	int **array_2d, i , j , size;
	int max_sum(0);
	int *row_sum,*col_sum,*row2_sum,*col2_sum;
	
	while(cin >> size)
	{
		array_2d  = new int*[size];
		row_sum  = new int[size];
		col_sum  = new int[size];
		row2_sum  = new int[size];
		col2_sum  = new int[size];

		for(i = 0 ; i < size; ++i)	
		{
			*(array_2d  + i)  = new int[size];	
			row_sum[i] = 0;

			for(j = 0 ; j < size ; ++j)
			{	
				cin >> *(*(array_2d + i) + j);
				row_sum[i] += *(*(array_2d + i) + j);			
			}
			row2_sum[i] = row_sum[i];
		}

		for(int i = 0 ; i < size ; ++i)
		{
			col_sum[i] = 0;

			for(int j = 0 ; j < size ; ++j)
			{
				col_sum[i]  += *(*(array_2d + j) + i);		
			}
			col2_sum[i] = col_sum[i];		
		}	

		Get_Max_Sum(array_2d , row_sum ,row2_sum , col_sum , col2_sum, size);

		delete(*array_2d);
		delete(row_sum);
		delete(col_sum);
		delete(row2_sum);
		delete(col2_sum);
	}

	return 0;
}

void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size)
{
	int row(0),col1(0),col2(0);
	int real_sum(array_2d[0][0]);
	int sum(0);

	col2  = col1 + 1;

	while(row < size && col1 < size - 1)
	{
		if(col2 == 1)
			sum = array_2d[row][col1] + array_2d[row][col2] ;
		else
			sum += array_2d[row][col2];
		
		if(real_sum < sum)
			real_sum = sum;	

		if(col2 < size - 1)
		{
			++col2;
		}
		else
		{
			for(int i = row + 1 ; i < size ; ++i)
			{
				sum += row_sum[i];
				
				if(real_sum < sum)
					real_sum = sum;				
			}

			++col1;
			col2 = col1 + 1;
			
			for(int i = 0 ; i < size ; ++i)
				row_sum[i] = row2_sum[i] - array_2d[i][col1 - 1];				
					
			sum = 0;
		}

		if(col1 >= size - 1)
		{
			++row;
			
			col1 = 0;
			col2 = col1 + 1;

			for(int i = 0 ; i < size ; ++i)
				row2_sum[i] = row_sum[i];
		}		
	}
	
	
	int col(0),row1(0),row2(0);
	sum = 0;

	row2  = row1 + 1;
	
	while(col < size && row1 < size - 1)
	{
		if(row2 == (row1 + 1) )
			sum = array_2d[row1][col] + array_2d[row2][col] ;
		else
			sum += array_2d[row2][col];
		
		if(real_sum < sum)
			real_sum = sum;	

		if(row2 < size - 1)
		{
			++row2;
		}
		else
		{
			for(int i = col + 1 ; i < size ; ++i)
			{
				sum += col2_sum[i];
				
				if(real_sum < sum)
					real_sum = sum;				
			}

			++row1;
			row2 = row1 + 1;

			for(int i = 0 ; i < size ; ++i)
				col2_sum[i] = col2_sum[i] - array_2d[row1 - 1][i];				
						
			sum = 0;
		}

		if(row1 >= size - 1)
		{
			++col;
			
			row1 = 0;
			row2 = row1 + 1;

			for(int i = 0 ; i < size ; ++i)
				col2_sum[i] = col_sum[i];			
		}		
	}

	cout << real_sum << endl;
}

Thanks in Advance.