108 - Maximum Sum

[Wei]

I've gotton some WA...
But I don't even know where the wrong is...
Could someone can help me???

Code: Select all

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,a[102][102],i,j,k,l,max;
    scanf("%d",&n);
	  max=-999;
	  for(i=1;i<=n;i++)
	       for(j=1;j<=n;j++)
                             scanf("%d",&a[i][j]);
	  for(i=1;i<=n;i++)
	       for(j=1;j<=n;j++)
	             a[i][j]=a[i-1][j]+a[i][j];
	  for(i=1;i<=n;i++)
	       for(j=1;j<=n;j++)
                             a[i][j]=a[i][j]+a[i][j-1];
                  for(i=1;i<=n;i++)
	       for(j=1;j<=n;j++)
	              for(k=0;k<=i;k++)
		       for(l=0;l<=j;l++)
		       {
		              if(i!=k||j!=l)
		               	  if(max<a[i][j]-a[k][l])
  		               	      max=a[i][j]-a[k][l];
         	                        }
	  printf("%d\n",max);
    /*system("PAUSE");*/
    return 0;
}

[emotional blind]

Look at this input

SAMPLE INPUT

Code: Select all

3
-100 -100 -100
-100    0 -100
-100 -100 -100

your out put is

Code: Select all

-100

But out put should be

Code: Select all

0

[58050zz]

1. If a sub-array has maximum sum, it must begins with a positive number. Because if it begins with a negative number, it will only make it smaller.

how to do if i have

-1 5 5
5 0 0
5 0 0

[58050zz]

B[i,j]:=b[i-1,j]+b[i,j-1]-b[i-1,j-1]+a[i,j] ...

And the whole program complexity is O(n^4)..

Try to implement this (this is quite an easy algoritm so try it )

Good Luck

if u have free time
plz give some help
i think i use ur algo with correct way
but still get WA
can u give me some samples

Code: Select all

#include <iostream>
using namespace std;



int main()
{
	int a[101][101];
	int b[101][101]={0};
	int i,j,k,n=0;
	int max=-999;
	int temp;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]>max)
			{
				max=a[i][j];
			}
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
			if(b[i][j]>max)
			{
				max=b[i][j];
			}
		}
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			{
				if(k<j)
				{
				temp=b[i][j]-b[i][k];
				if(temp>max) max=temp;
				}
				if(k<i)
				{
				temp=b[i][j]-b[k][j];
				if(temp>max) max=temp;
				}
				if(k<i && k<j)
				{
				temp=b[i][j]-b[k][j]-b[i][k]+b[k][k];
				if(temp>max) max=temp;
				}
			}
		}
	}
	cout<<max<<endl;
	return 0;
}

[58050zz]

http://acm.uva.es/p/v1/108.html

help WA

Code: Select all

#include <iostream>
using namespace std;

void output(int a[][101],int b[][101],int n)
{
	int i,j;
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("%3d",a[i][j]);
		}
		printf("\n");
	}

	printf("=========\n");

	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("%3d",b[i][j]);
		}
		printf("\n");
	}

}

int main()
{
	int a[101][101];
	int b[101][101]={0};
	int i,j,k,n=0;
	int max=-999;
	int temp;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]>max)
			{//if max
				max=a[i][j];
			}
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
			//make b table
			//pic1
			if(b[i][j]>max)
			{//if max
				max=b[i][j];
			}
		}
	}
	//output(a,b,n);
	for(i=1;i<=n;i++)
	{//implement b table
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			{
				if(k<j)
				{//pic 2
					temp=b[i][j]-b[i][k];
					if(temp>max) max=temp;
				}
				if(k<i)
				{
					temp=b[i][j]-b[k][j];
					if(temp>max) max=temp;
				}
				if(k<i && k<j)
				{//pic 3
					temp=b[i][j]-b[k][j]-b[i][k]+b[k][k];
					if(temp>max) max=temp;
				}
			}
		}
	}
	cout<<max<<endl;
	return 0;
}

[58050zz]

my algorithm

http://online-judge.uva.es/board/viewto ... hlight=108

Thanks for explanation...

but I will write you here a simplier (I hope method....

Let us make a table B...

the B[i,j] = sum (from 1 to i and form 1 to j of A)

that means that B[1,1]=A[1,1] B[1,2]:=A[1,1]+A[1,2]; ... B[2,2]= A[1,1]+A[1,2]+A[2,1]+A[2,2]....

and if you have this table the sum of the rectangle for exmple form 2,2 to 4,5 is equal to :
B[4,5]-B[4,1]-B[1,5]+B[1,1] (if you don't believe you can check

So if you have table B you can solve this problem in O(n^4) -- check all the possibilities in O(1) time as I wrote before...

If you are clever you can count the B table in O(n^2) time...
because B[i,j]:=b[i-1,j]+b[i,j-1]-b[i-1,j-1]+a[i,j] ...

And the whole program complexity is O(n^4)..

Try to implement this (this is quite an easy algoritm so try it )

Good Luck

[58050zz]

..

[Emilio]

Your algorithm is O(n^3) not O(n^4) how cyfra wrote

[Sakib]

Anyone please help me to show the way how i can implement the O^4 or O^3 algorithm here.
I used O^6 but got TLE.
Please Help!

[mohiul alam prince]

Hi
this is the O^3 algorithm

*
- first find out the maximum value for row-1
- then add first row and second row and find out the maximum value.
- then add third row first row and second row and find out the maximum value
- then forth row and up to N and continue.

*
- then again first select second row and find out maximum value
- then add third row and find out the maximum value.
- and N continue.

thanks:)
MAP

[nicu_ivan]

Hye, I have a problem (time limit exedeed). I used a O^6 algoritm and I need help In makeing a faster algoritm.
Here is my code:

Code: Select all

var n,i,j,k,r,suma,yes,max:longint;
    nr:array[1..110,1..110] of longint;

function sumarit(i1,j1,i2,j2:longint):longint;
var i,j,suma:longint;
begin
     suma:=0;
     for i:=i1 to i2 do
     for j:=j1 to j2 do
        suma:=suma+nr[i,j];
     sumarit:=suma;
end;

begin
     readln(n);
     for i:=1 to n do
     for j:=1 to n do
        read(nr[i,j]);
     suma:=0;
     for i:=1 to n do
     for j:=1 to n do
     for k:=1 to n do
     for r:=1 to n do
        begin
             yes:=sumarit(i,j,k,r);
             if yes>suma then
                suma:=yes;
         end;
     writeln(suma);
end.

Please give me a better idea. I really need one.

[Observer]

Hi,

For this task, an O(n^6) algorithm will never get accepted... Please search the board for related topics. There are more than 30 of them.

[Sakib]

Thanks for help.
I will try tour algorithm.

[dmn]

I don't know why i got wa. I think it's good and it's work with my all inputs.
If anyone can tell me what's wrong with this code i will be appreciative.

Code: Select all

//o(n^4)
#include<iostream>
using namespace std;
int main(void)
{
const int m = 100;
int array[m][m];
	int n;
	while(cin>>n){
		//read array
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				cin>>array[i][j];
		//calculate maximum summ
		int max=array[0][0];
		for(int k=0;k<n;k++)
			for(int i=0;i<n-k;i++){
				bool in=false;
				int Q,j;
				for(j=0,Q=array[i][j];j<n;j++){
					int q=0;
					for(int l=0;l<=k;l++)
						q+=array[i+l][j];
					if(q<0){
						if(in){
							in=false;
							if(Q>max) max=Q;
						}
						else if(q>max) max=q;
					}
					else{
						if(!in){
							in=true;
							Q=q;
						}
						else Q+=q;
					}
				}
				if(Q>max) max=Q;
			}
		cout<<max<<endl;
	}
	return 0;
}

[dmn]

Ok I know what's wrong and i solved it so don't bother it