## 108 - Maximum Sum

Moderator: Board moderators

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

### 108...With lots of WA~~!!!

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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Look at this input

SAMPLE INPUT

Code: Select all

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

Code: Select all

``-100``
But out put should be

Code: Select all

``0``

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
ImLazy wrote:
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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
cyfra wrote: 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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

### 108 Maximum Sum

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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
my algorithm

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

cyfra wrote: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
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

### ..

..

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Your algorithm is O(n^3) not O(n^4) how cyfra wrote

Sakib
New poster
Posts: 24
Joined: Fri Jan 28, 2005 5:27 pm

### Problem 108

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.
/* Sorry For Nothing */

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
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
New poster
Posts: 7
Joined: Wed Mar 16, 2005 7:27 pm

### 108 Maximum sum - Time limit exeeded

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
for i:=1 to n do
for j:=1 to n do
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sakib
New poster
Posts: 24
Joined: Fri Jan 28, 2005 5:27 pm
Thanks for help.
I will try tour algorithm.
/* Sorry For Nothing */

dmn
New poster
Posts: 2
Joined: Sun May 08, 2005 4:25 pm

### problem 108 WA(what's wrong with this code)

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){
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
New poster
Posts: 2
Joined: Sun May 08, 2005 4:25 pm

### Re: problem 108 WA(what's wrong with this code)

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