108 - Maximum Sum

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Sun Oct 03, 2004 4:15 pm

Here's an explanation how the one-dimnentional problem can be solved
in O(n)

say for an array [x1, x2, ..., xn] you need to find the maximum sum
of consecutive elements.

Say you start with an answer zero. You run a loop to add up the numbers.
If the sum gets bigger than your answer update it. But if the sum gets
< 0 then then set the sum = 0. This will work.

Why it works?
Say sum(xi, ..., xa) < 0. If you add upto xb then
sum = sum(xi, ..., xa) + sum(x(a+1), ... xb)
= < 0 + sum(x(a+1), ... xb) < sum(x(a+1), ... xb)
So when sum(xi, ..., xa) < 0 this sequence will be better left of from the
answer. Setting up sum = 0 will do that.

Did I explain it correctly or is it more confusing :(

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Sun Oct 03, 2004 6:38 pm

I got your idea. Thanks a lot.

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

Post by Zuza » Tue Oct 05, 2004 9:02 pm

As you found out your program is too slow because it runs in apx 10^1 (if n=100). We could solve this problem using DP in a similar way as if we would check for the maximum sum of consecutive element in an array (lets assume that there isn't any O(n) nor O(n log n) algorithm). First, we need a efficient way to answer the question: What is the sum of the elements from A to B. If we say that the element S[n] holds the sum of the elements from 0 to n (from the input), then sum[A,B]=S-S[A-1]. This works because we add all the elements to B, and then exclude which we don't need (from 0 to B-1). This method has its extension in 2d : if [a,b] is the sum of the subrect ((0,0),(a,b)), then the sum of the rect defined by ((x1,y1),(x2,y2)) equals S[x2,y2]-S[x1,y2]-S[x2,y1]+ [x1,y1]. Now you can tell the sum of a (sub)rectangle in O(1), not O(n^2). You can just check now all the subrects and get an "easy" AC.

And just note that there are still beter ways for finding the maximum subrect. :)

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Thu Oct 14, 2004 4:56 am


masumasu
New poster
Posts: 3
Joined: Thu Dec 09, 2004 3:06 pm

Problem in 108 with my solution ...plzzzzzzzz help

Post by masumasu » Sat Dec 11, 2004 10:20 am

hi i am having problem in 108 ...plzzzzzzzz help dont know whjere
C++

#include <iostream>

using namespace std;
int **sumfromindex,**values;

int main()
{
int Numrows;
int maxsum = -500;

cin >> Numrows;
values = new int*[Numrows];
sumfromindex = new int*[Numrows];
for (int i=0;i<Numrows;i++)
{
sumfromindex[i] = new int[Numrows*Numrows];
/*for (int j=0;j<Numrows;j++)
sumfromindex[i][j] = new int[Numrows];*/
}
for (int i=0;i<Numrows;i++)
{
values[i] = new int[Numrows];
for (int j=0;j<Numrows;j++)
{
cin >> values[i][j];
}
}
for (int rowindex=0;rowindex<Numrows;rowindex++)
{
sumfromindex[rowindex][0] = values[rowindex][0];
//cout << rowindex << " 0 " << " 1 " << " 1 " << sumfromindex[rowindex][0] << endl;
if (sumfromindex[rowindex][0]>=maxsum)
{
maxsum = sumfromindex[rowindex][0];
}
}
for (int rowindex=0;rowindex<Numrows;rowindex++)
{
int colindex=0;
for (int nocols = 1;nocols<Numrows;nocols++)
{
sumfromindex[rowindex][nocols] = sumfromindex[rowindex][nocols-1]+values[rowindex][colindex+nocols];
//cout << rowindex << " 0 " << " 1 " << (nocols+1) <<" = " << sumfromindex[rowindex][nocols]<<endl;
if (sumfromindex[rowindex][nocols]>=maxsum)
{
maxsum = sumfromindex[rowindex][nocols];
}
}
for (int norows = 1;norows<Numrows-rowindex;norows++)
{
sumfromindex[rowindex][norows*4] = sumfromindex[rowindex][(norows-1)*4]+values[rowindex+norows][0];
//cout << rowindex << " 0 " << (norows+1)*4 << " 1 " <<" = " << sumfromindex[rowindex][norows*4]<<endl;
if (sumfromindex[rowindex][norows*4]>=maxsum)
{
maxsum = sumfromindex[rowindex][norows*4];
}
}
}
/*for (int rowindex=0;rowindex<Numrows;rowindex++)
for (int colindex = 0;colindex<Numrows;colindex++)
for (int nocols = 1;nocols<Numrows-colindex;nocols++)
{
sumfromindex[rowindex*4+colindex][nocols] = sumfromindex[rowindex*4+colindex][nocols-1]+values[rowindex][colindex+nocols];
if (sumfromindex[rowindex*4+colindex][nocols]>=maxsum)
{
maxsum = sumfromindex[rowindex*4+colindex][nocols];
Rowindex = rowindex;
Colindex = colindex;
offsetcols = nocols;
offsetrows = 0;
}
//if (sumfromindex[rowindex][colindex][0][nocols] <0)
// break;
}
*/
for(int rowindex=0;rowindex<Numrows;rowindex++)
for (int norows=1;norows<Numrows-rowindex;norows++)
for (int nocols=1;nocols<Numrows;nocols++)
{
sumfromindex[rowindex][norows*4+nocols] = sumfromindex[rowindex][(norows-1)*4+nocols]
+ sumfromindex[rowindex+norows][nocols];
//cout<<rowindex<< " 0 " <<(norows+1)*4<< " "<< (nocols+1)<<" = " << sumfromindex[rowindex][norows*4+nocols]<<endl;
if (sumfromindex[rowindex][norows*4+nocols]>=maxsum)
{
maxsum = sumfromindex[rowindex][norows*4+nocols];
}
}

for(int rowindex=0;rowindex<Numrows;rowindex++)
{
for (int colindex=1;colindex<Numrows;colindex++)
for (int norows=0;norows<Numrows-rowindex;norows++)
for (int nocols=0;nocols<Numrows-colindex;nocols++)
{
int sum = sumfromindex[rowindex][norows*4+nocols+colindex]-sumfromindex[rowindex][norows*4+colindex-1];
//sumfromindex[rowindex*4+colindex][norows*4+nocols] = sumfromindex[rowindex*4+colindex][(norows-1)*4+nocols]
// + sumfromindex[(rowindex+norows)*4+colindex][nocols];
//cout<<rowindex<< " "<< colindex <<" " << (norows+1)<< " "<< (nocols+1)<<" = " << sum<<endl;
if (sum>=maxsum)
{
maxsum = sum;
}
}
}
cout << maxsum << endl;
}

User avatar
BenderBendingRodriguez
New poster
Posts: 13
Joined: Wed Sep 08, 2004 10:54 am

108 - Maximum Sum - Time Limit Exceeded

Post by BenderBendingRodriguez » Tue Dec 21, 2004 8:45 pm

hi @ all,

this is my C++ code for problem 108.
i'm sure it's working fine, but i always get Time Limit Exceeded.
why? :-?

Code: Select all

/* @JUDGE_ID: 48058YJ 108 C++ "" */

//@BEGIN_OF_SOURCE_CODE

#include <iostream>

using namespace std;

int main(void)
{
  int maxSum = 0;
  int maxSumTemp = 0;

  int n;
  do
  {
    cin >> n;
  }
  while(n <= 0);

  int array_2D[n][n];
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < n; j++)
    {
      do
      {
        cin >> array_2D[i][j];
      }
      while((array_2D[i][j] < -127) || (array_2D[i][j] > 127));
    }
  }
  
  for(int i = 0; i < n; i++)
  {
    for(int j = i; j < n; j++)
    {
      for(int k = 0; k < n; k++)
      {
        for(int l = k; l < n; l++)
        {
          for(int x = i; x <= j; x++)
          {
            for(int y = k; y <= l; y++)
            {
              maxSumTemp += array_2D[x][y];
            }
          }
          maxSum = maxSumTemp > maxSum ? maxSumTemp : maxSum;
          maxSumTemp = 0;
        }
      }
    }
  }
  
  cout << maxSum << endl;

  return 0;
}

//@END_OF_SOURCE_CODE

thx
Bender
When you do things right, people won't be sure you've done anything at all.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed Dec 22, 2004 3:37 am

naive O(N^6) is too slow.. though maybe if you memoize it some, it might be fast enough..

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

#108 WA plz help me @_@

Post by lazenca » Tue Dec 28, 2004 5:59 am

I guess my code is correct...
what's the problem? :o

And I need some test data..

Code: Select all

#include <iostream.h>
#include <limits.h>
/*
   <INPUT>
   N             N: positive integer, size of the square two dimentional array.
   .....            This is followed by N*N integers separated by white-space(row-major order)
   .....

   <OUTPUT>
   The output if the sum of the maximal sub-rectangle
   -
   <CONDITION>
   The sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
   A sub-rectangle is any contigious sub-array of size 1 X 1 or
   greater located within the while array.
   
   0 < N <= 100
   -127 <= elements <= +127
*/

void main()
{
	int   sub_max = INT_MIN, sub_cumulative = 0, total_cumulative = 0, total_max = INT_MIN;
	int   in_data, i, j, N;
	
	cin >> N;
	
	for (i = 0;   cin >> in_data;   j++)   {
	
		if ((sub_cumulative += in_data) > sub_max)
			sub_max = sub_cumulative;

		if (++i % N == 0)   {
			if ((total_cumulative += sub_max) > total_max)
				total_max = total_cumulative;
			
			sub_max = INT_MIN;
			sub_cumulative = 0;
			i = 0;
		}

	cout << total_max << endl;
}
I see the red...
I saw the rain..

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Dec 28, 2004 8:46 am

The number of curly braces in your code is mismatched. I couldn't quite figure out where the required closing bracket should be placed. Please make the necessary corrections in your code.

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

hm...=_=

Post by lazenca » Tue Dec 28, 2004 9:50 am

sorry...It's my mistake when I wrote this post.... :oops:

here are correct codes.

Code: Select all

#include <iostream.h> 
#include <limits.h> 
/* 
   <INPUT> 
   N             N: positive integer, size of the square two dimentional array. 
   .....            This is followed by N*N integers separated by white-space(row-major order) 
   ..... 

   <OUTPUT> 
   The output if the sum of the maximal sub-rectangle 
   - 
   <CONDITION> 
   The sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. 
   A sub-rectangle is any contigious sub-array of size 1 X 1 or 
   greater located within the while array. 
    
   0 < N <= 100 
   -127 <= elements <= +127 
*/ 

void main() 
{ 
   int   sub_max = INT_MIN, sub_cumulative = 0, total_cumulative = 0, total_max = INT_MIN; 
   int   in_data, i, j, N; 
    
   cin >> N; 
    
   for (i = 0;   cin >> in_data;   j++)   { 
    
      if ((sub_cumulative += in_data) > sub_max) 
         sub_max = sub_cumulative; 

      if (++i % N == 0)   { 
         if ((total_cumulative += sub_max) > total_max) 
            total_max = total_cumulative; 
          
         sub_max = INT_MIN; 
         sub_cumulative = 0; 
         i = 0; 
      } 

   }

   cout << total_max << endl; 
} 
I see the red...
I saw the rain..

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Thu Dec 30, 2004 9:10 am

Hi, the problem is you are processing only one case. That is you assume that after one set of input, there will not be anymore.

But you should continue to take input until you encounter EOF while trying to read the value of N.

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

Post by lazenca » Thu Dec 30, 2004 10:53 am

Thanks!
I modified my code...but still WA.. :(
what is missing things?
or I misunderstood your advice?

Code: Select all


void main()
{
	int   sub_max, sub_cumulative, total_cumulative, total_max;
	int   in_data, i, N, limits;
	
	while (cin >> N)   {

		/*   initialize...   */
		sub_max = INT_MIN, sub_cumulative = 0, total_cumulative = 0, total_max = INT_MIN;
		limits = N * N;
	
		for (i = 1;    i <= limits;    i++)   {
			
			cin >> in_data;
			if ((sub_cumulative += in_data) > sub_max)
				sub_max = sub_cumulative;

			if ((i % N) == 0)   {
				if ((total_cumulative += sub_max) > total_max)
					total_max = total_cumulative;
				
				sub_max = INT_MIN;
				sub_cumulative = 0;
			}
		}
		cout << total_max << endl;
	}   /*   end of while()   */
}
I see the red...
I saw the rain..

Iwashere
New poster
Posts: 20
Joined: Mon Aug 11, 2003 1:50 pm
Location: Singapore

Post by Iwashere » Thu Dec 30, 2004 5:54 pm

Input:

Code: Select all

4
-100 4 4 -100
-100 4 4 -100
-100 4 4 -100
-100 4 4 -100
your output:

Code: Select all

-92
my output:

Code: Select all

32
and i think this problem just consists of one test case, cos my AC prog handles only one...

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

Post by lazenca » Mon Jan 03, 2005 6:07 am

first of all, thanks....

I noticed that my code has many fault...oooooo......
I see the red...
I saw the rain..

User avatar
lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

Post by lazenca » Mon Jan 03, 2005 10:16 am

I modified some part of my code...
But still got WA...It seems to be correct.

Is my algorithm correct?

Code: Select all

#include <iostream.h>
#include <limits.h>

#define   ONLINE_JUDGE


void main()
{
	int   i = 0, N;
	int   in_data, sub_cumulative, sub_max;
	
	cin >> N;

	/*   first element must be include..   */
	cin >> sub_cumulative;
	sub_max = INT_MIN;
	

	i = 2;

	while (cin >> in_data)   {

		/*   ignore negative values  */
		sub_cumulative = (in_data > sub_cumulative + in_data) ? 
							((in_data > 0) ? 
								in_data : 
								sub_cumulative) : 
								((sub_cumulative + in_data > 0) ? 
									sub_cumulative + in_data :
									sub_cumulative);

		if (sub_cumulative > sub_max)
			sub_max = sub_cumulative;

		if ((i % N) == 0)   {
			sub_cumulative = sub_max;
			sub_max = INT_MIN;
		}
		
		i++;
		
	}   /*   end of while()   */

	cout << sub_cumulative << endl;
}
I see the red...
I saw the rain..

Post Reply

Return to “Volume 1 (100-199)”