108 - Maximum Sum

[rezaee]

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]

You should search before posting a new topic about one problem... there are a lot of threads about this problem...

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

[huan086]

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]

ok.

but my code does work correctly.

in my compiler.



i dont know what to do.

[rezaee]

help me.

[rezaee]

i get a WA.

please help me.

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]

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.

[FilePointer]

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]

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)]

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)

[namanh]

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) {
    String input = ReadLn(255);
    
    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));
  }
  
  static String ReadLn (int maxLg) 
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                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]

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]

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.
So Please HELP me out.

[Jan]

Search the board first. Dont open a new thread if there is one already.

[renato_ferreira]

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;

    scanf("%d", &lado);

    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.