## 108 - Maximum Sum

Moderator: Board moderators

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

### 108 maximum sum

oh.ok.

but i get WA.

#include <iostream.h>

int n;
int b[101][101];

int main()
{
int a[101][101];
int i,j,k;
int max;
int s;
while(cin>>n)
{max=-127;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[j];
if(a[j]>max)
{
max=a[j];
}
b[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];
if(b[j]>max)
{
max=b[j];
}
}
}

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{
s=b[j]-b[k];
if(s>max) max=s;
}
if(k<i)
{
s=b[i][j]-b[k][j];
if(s>max) max=s;
}
if(k<i && k<j)
{
s=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(s>max) max=s;
}
}
}
}
cout<<max<<endl;}
return 0;
}

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

instead of posting your code, first try to discuss your algorithm. Then, if you want to post the code, use de 'code' tag.

good luck
Miguel Oliveira

huan086
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm
b[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];

You accessed b[0] without initialising the array... I believe you need to do so in c++. (not needed in VB though)

Search through the forum and see how others had done it. Your code is longer than the typical ones.

And debug before posting

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

### 108 maximum sum

ok.

but my code does work correctly.

in my compiler.

i dont know what to do.

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

### 108 maximum sum

help me.
Last edited by rezaee on Wed Dec 20, 2006 9:16 pm, edited 1 time in total.

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

### 108 maximum sum

i get a WA.

Code: Select all

``````#include <iostream.h>

int n;
int b[101][101];

void sefr(void)
{for(int i=0;i<=n;i++)
{b[0][i]=0;b[i][0]=0;}

}

void main()
{
int a[101][101];
int i,j,k;
int max;
int temp;
while(cin>>n)
{if(n==0)break;
max=-127;
sefr();
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;}}``````
please give me some test case.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Check the case

Input:

Code: Select all

``````20
-86 -20 87 108 -83 42 -124 -94 60 112 -32
-32 -51 125 -111 109 63 85 110 -46 -121
-58 -50 26 -90 15 -46 -26 -44 -122 -35
-76 109 -64 -43 -105 40 -93 78 77 16
-31 85 116 -49 -53 -31 -66 76 111 -80
-23 -105 -10 20 -18 -74 -76 117 -114 -51
103 -122 -70 -94 -111 -12 -110 12 81 34
-37 -47 -28 18 -77 89 119 41 106 122
1 -13 -63 14 -17 -6 109 34 -84 -13
-73 19 -24 55 -9 -74 -85 107 94 116
-122 -78 -49 -118 113 80 -116 -74 74 49
58 22 75 23 92 -125 -109 125 65 -111
-97 109 -106 43 -95 68 -108 79 -60 -62
3 -16 -78 69 -12 125 -26 30 -10 30
-80 86 56 28 112 -48 -59 124 101 -80
84 94 -102 -34 -29 8 79 20 -2 -57
112 -43 10 1 -19 -72 89 -95 -2 -36
109 67 -72 -121 -76 -64 122 -94 -123 -6
17 -74 87 26 16 -112 91 -105 85 31
-24 41 -84 85 -1 -97 115 -9 -48 -98
94 -62 -16 73 22 72 64 -24 86 -23
-84 107 97 72 -65 8 -42 -94 -64 51
-70 117 -59 -74 83 71 116 53 34 -119
109 82 16 87 0 -55 35 51 -75 46
82 -42 -50 -74 -56 53 66 -96 -91 10
-43 -80 38 56 79 -30 -86 -122 1 -93
125 2 14 79 -4 -5 -91 -51 -38 115
44 -30 37 103 -125 -77 88 -34 -33 -116
26 14 -28 83 -24 30 3 85 -42 -69
-66 -70 -85 15 -50 -38 -13 94 -23 -41
92 -54 5 -122 -27 -8 102 -81 -50 -72
83 -84 56 -53 56 87 114 -15 -93 -18
-30 104 72 66 118 110 -111 109 -87 -119
90 88 107 -118 99 79 -111 49 -104 106
3 -52 36 20 -29 -80 -92 106 89 -111
51 59 60 99 -63 119 -50 117 -6 53
-77 81 -116 -68 112 -100 47 41 7 17
58 28 122 54 26 12 100 1 121 45
88 -19 124 -125 -72 85 -48 7 -58 -118
-8 20 -113 -24 -107 -35 120 -4 -110 ``````
Output:

Code: Select all

``1864``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

FilePointer
New poster
Posts: 1
Joined: Mon Feb 05, 2007 8:41 am

### 108 Why Compile Error at Submit??

The Code is...

Code: Select all

``````#include <iostream>

using namespace std;

short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };

int main( int argc, char **argv )
{
int MaxSum = -999999;
int size;

cin >> size;

for( int i = 1; i <= size; i++ ) {
for( int j = 1; j <= size; j++ ) {
cin >> Matrix[ i ][ j ][ i ][ j ];
}
}

for( int StartI = 1; StartI <= size; StartI++ ) {
for( int StartJ = 1; StartJ <= size; StartJ++ ) {

for( int EndI = StartI; EndI <= size; EndI++ ) {
for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {

short RectangleSum, LineSum;
if( StartJ == EndJ )
RectangleSum = 0;
else
RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];

if( StartI == EndI )
LineSum = 0;
else
LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];

short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;

short NewRectangleSum = RectangleSum + NewLineSum;
Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;

if( MaxSum < NewRectangleSum )
MaxSum = NewRectangleSum;
}
}

}
}

cout << MaxSum;

return 0;
}

``````
There isn't Error in VS.NET 2003 & Cygwin( gcc 3.4.4 ) & Dev-C++ lastest version

What is reason for Compile Error?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
change this line

Code: Select all

``short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, }; ``
to

Code: Select all

``short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] ; ``
But it will get MLE now.

Fauhat(AUST)
New poster
Posts: 3
Joined: Thu Mar 22, 2007 6:21 am

### presentation error in 108

Dear judges,

I am getting presentation error in 108(maximum sum). But I cannot understand why it is happening. I am printing only the result without giving any space and new line as the sample output indicates.

Will you kindly help me replying this mail saying the correct form of printing the result?

Regards,

Fauhat Ali Khan Panni(AUST)
*fauhat A.K. panni*

namanh
New poster
Posts: 1
Joined: Fri Mar 23, 2007 9:05 pm

### 108 - WA ??? Need help !!!

Here's my code in Java. I have tried all test that i found on this forum, and the result is correct in all case. But i still got WA.
Anybody know why ?

Code: Select all

``````import java.util.*;
import java.io.*;

class Main {
static void main(String[] args) {

StringTokenizer idata = new StringTokenizer (input);
int n = Integer.parseInt(idata.nextToken());

int[][] a = new int[n][n];
int i=0,j=0;

while(i < n && (input = ReadLn(255)) != null ) {
idata = new StringTokenizer(input);
while(idata.hasMoreTokens()) {
a[i][j] = Integer.parseInt(idata.nextToken());
j++;
if(j == n) {
j=0;
i++;
}
}
}

System.out.println(maxTwoDimension(a));
}

{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

static int maxTwoDimension(int[][] a) {
int n = a.length;
int m = a[0].length;
int[][] best = new int[m][m];
int[][][] b = new int[n][m][m];

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int k = j; k < m; k++){
if(j==0 && k ==0) b[i][j][k] = a[i][0];
if(j==0 && k > 0) b[i][j][k] = b[i][j][k-1] + a[i][k];
if(j > 0 )
b[i][j][k] = b[i][0][k] - b[i][0][j-1];
}
}
}
int[] temp = new int[n];
for(int j = 0; j < m; j++) {
for(int k = j; k <m; k++) {
for(int i = 0; i < n; i++)
temp[i] = b[i][j][k];
best[j][k] = maxOneDimension(temp);
}
}
int max = best[0][0];
for(int j = 0; j < m; j++) {
for(int k = j; k < m; k++) {
if (best[j][k] > max) max = best[j][k];
}
}

return max;
}

static int maxOneDimension(int[] temp) {
int n = temp.length;
int[] best = new int[n];
for(int i = 0; i < n; i++)
best[i] = temp[i];

int max = best[n-1];
for(int i = n-2; i >=0; i--) {
if(best[i+1] >0) best[i] +=best[i+1];
if(best[i] > max) max = best[i];
}

return max;
}
}
``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
without giving any space and new line as the sample output indicates
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.

duleb
New poster
Posts: 4
Joined: Mon Jun 11, 2007 8:06 am

the source code is

#include<iostream>
using namespace std;
main()
{
int f=0,s=0;
short int a[90][90],i,j=0,k=0,m=0,x,y,n=0;
cin>>n;
for(x=0;x<n;x++)
for(y=0;y<n;y++)
cin>>a[x][y];
x=0;
while( k<=n)
{
for(i=m;i<n;i++)
for(j=0;j<=x;j++)
{
f+=a[j];
if(f>s)
s=f;
}
if(i==n)
{
x++; f=0;
}
if(x==n)
{
m++; x=0;
}
if(m==n)
{
k++; x=m=0;
}
}
cout<<s;
}

On My PC It Takes almost no time to execute (On Fedora 6) ;while submitting ,it is showing that program is exceeding 10 second.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Search the board first. Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
Hello, I need to optimize this code (TLE), but I have no idea how to do this, can you help me?

Code: Select all

``````#include <stdio.h>

int max = -9999, matriz[101][101], lado;

void busca(int altura, int largura);

int main()
{
int valor, i, j;

for (i = 0; i < lado; i++)
{
for (j = 0; j < lado ; j++)
{
scanf("%d", &valor);

matriz[i][j] = valor;
}
}

for (i = 0; i <= lado; i++)
{
for (j = 0; j <= lado; j++)
{
busca(i, j);
}
}

printf("%d", max);

return 0;
}

void busca(int altura, int largura)
{
int i, j, k, soma, g;

for (i = 0; i < (lado - altura); i++)
{
for (j = 0; j < (lado - largura); j++)
{
soma = 0;

for (g = i; g < (lado - altura); g++)
{
for (k = j; k < (lado - largura); k++)
{
soma += matriz[g][k];
}
}

if (soma > max)
{
max = soma;
}
}
}
}
``````
Thank you.