108 - Maximum Sum

[dootzky]

i don't know how - i don't know why - BUT

this logic by "imlazy" is an imperative!! i mean - OMG!!
my program was returning TLE, and it was expected, because i was doing brute force O(n^6) - [what ever that may mean, i saw others use these terms, so i assume it's some time/complexity mark..?!]

so i was brutally adding all possible rectangles.
and TLE, TLE and more TLE - 10+ sec.

then, i added these little 2 conditions:
1) if ( BOARD[j] <=0 ) don't_even_try_to_find_it's_sum(); else sum();
in my "sum()" function, i added this part:
2) if ( sum<=0 ) break;

and i got accepted, in 1.49 sec. O-M-G!!

i'm currently very very happy little man!
thx for the idea,
best regards,
dootzky

[dootzky]

and really, "58050zz" asked a really good question, that even i don't uderstand, besides my ACC.

if input is:

-1 5 5
5 0 0
5 0 0

my code would go something like:
first elemet - B[0][0] = -1
ok, it's negative, skip it!
and all the other test would be less then 19.. no?!

BUT!! (there's always some buts...) - i tryed this input, and my code gives the right answer - 19. o.m.g. i seriously don't get it.
anyone?!?

here is my code, it's really small and simple, but i still don't get it.
i'll remove it in a few days, but i hope until then someone can explain the "stand-alone behaviour" of my program. how does it ever get the sum of 19?! HOW GOD?!! HOOOOOW?!

Code: Select all

code removed

cheerz,
dootzky

[Ronald29]

how if all the number in the array is negative?
your program will print 0 because you skip all the number in the array right?

[dootzky]

exactly!

therefore, how come that my code is ACCEPTED?!

anyway, the problem description says "maximum sum", and since i declare MAX as 0 (max=0), and all numbers in the array are negative, the MAXIMUM of all negative is still - 0. ??

i dunno if this makes any sense at all, or better yet, how the hell did my code give the right solution for test

-1 5 5
5 0 0
5 0 0

??? the anser is 19, but i'm totally sure that my code skips the first element (-1). how can it calculate solution 19?!?!

i seriously think somebody is crazy here. me, perhaps.

cheers,
i still hope someone will explain this code to me.
maybe that guy "shanzoor", or that german dude, "michael kw.", or our poland friend "Krzysztof Duleba", or somebody who knows math & algos little bit better then us, amateurs
dootzky

[rajsekar_manokaran]

Hi dootzky

your code does not see is the first element is > 0.
you have used br[p.q] > 0

The comma operator does not do anything. So its as if you see if the memory address of b[q][0] is > 0 which is a tautology. Thus, you basically run the function on every pair (i,j).

[dootzky]

aah, i see your point.

very nice conclusion. my bad

thx mon, i really though there's something else wrong, but now i see that it was my typo.

cheers,
dootzky

[Crichton]

Hi,
i have WA with my code and don't know why...javascript:emoticon(':(')
plz help me
my code:

Code: Select all

#include <iostream> 
using namespace std;


int main(){ 
  int n,max=-150,sum=0;
  cin>>n;
  int a[n+1][n+1]; 
  int b[n+1][n+1];
  b[0][0]=0;
  for(int i=1;i<=n;i++){
    b[i][0]=0;
    for(int j=1;j<=n;j++){
      b[0][j]=0;
      cin>>a[i][j];
      b[i][j]=0;
      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(int i=1;i<=n;i++){ 
    for(int j=1;j<=n;j++){ 
      for(int k=1;k<=n;k++){ 
        if(k<=j){ 
          sum=b[i][j]-b[i][k]; 
          if(sum>max) max=sum; 
        } 
        if(k<=i){ 
          sum=b[i][j]-b[k][j]; 
          if(sum>max) max=sum; 
        } 
        if(k<=i and k<=j){
          sum=b[i][j]-b[k][j]-b[i][k]+b[k][k]; 
          if(sum>max) max=sum; 
  }}}} 
  cout<<max<<endl;
}

thx for your help

[tan_Yui]

Try this.

Code: Select all

3
-127 -125 -123
-121 -119 -117
-115 -113 -111

Output is -111.

By the way, my compiler (Borland C++ Compiler 5.5) shows compile error for your code. Other compiler (e.g. acm judge system) may not fail, but I couldn't compile normally without any editing in my environment.
Following is the description with my opinion.
Please ignore the information if it is not necessary for you.

int a[n+1][n+1];
int b[n+1][n+1];

'n' is parameter. I think [101] is enough instead of [n+1].

if(k<=i and k<=j){

I changed 'and' to '&&'.

Thank you.

[Animesh_nayan]

I hve the following code which gives correct output,,for all possible test cases,,but time limit is exceeded ..Can neone help me out...

#include<iostream>
using namespace std;


int main()
{
int a[100][100];

int i,j,s,max=-150,m,n,k,l;
cin>>n;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin>>a[j];
}




for(i=0;i<n*n;i++)
{
for(j=i;j<n*n;j++)
{
if((j%n)>=(i%n))
{
int a1,a2,b1,b2,s=0;
a1=i/n;
a2=j/n;
b1=i%n;
b2=j%n;
for(int i=a1;i<=a2;i++)
{
for(int j=b1;j<=b2;j++)
{
s+=a[j];
}
}


if(s>max)
max=s;
}
}
}
cout<<max;
return 0;
}

[Artikali]

you used O(n^5) algo, you must use O(n^3) algo, O(n^4) algo also may be.
see topics about problem

[emotional blind]

use this useful link

Code: Select all

http://acm.uva.es/board/viewtopic.php?p=2709#2709 

[Qodeus]

Hello! I have read a lot of posts on this board about this problem, but I still cannot realy understand how to solve the problem.
I understand that, first, I should create another matrix which will at position [a] hold the sum of all the elements in the sub-matrix that has an upper-left corner in [0][0] and its lower-right corner is [a].

For the sample input

Code: Select all

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

that matrix should look like:

Code: Select all

0  -2   -9   -9
9   9   -4   -2
5   6  -11   -8
4  13   -4   -3

But here comes my problem. I do not understand how to compute the sum of a sub-matrix that has an upper-left corner other than [0][0].
If someone could help me I would be very grateful!

Thanx in advance!

[emotional blind]

when upper left corner is [p][q]
then sum of submatrix from [p][q] to [a] equals
sum[a]-sum[a-1]-sum[a][b-1]+sum[a-1][b-1]

[Qodeus]

Thank you for your reply. But it seams that you have made a mistake because you don't use p or q.
But never mind, I have found the formula. If anyone ever needs this:
If upper-right corner is [p][q] and the lower-left corner is [a], then the sum of that rectangle is:
sum[a] - sum[a][q - 1] - (sum[p - 1] - sum[p - 1][q - 1])

[emotional blind]

Correction:
sum[a]-sum[p-1]-sum[a][q-1]+sum[p-1][q-1]

sorry for my mistake