108 - Maximum Sum

Tahseen Mohammad · 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 · Post by **jambon_vn** » Sun Oct 03, 2004 6:38 pm

I got your idea. Thanks a lot.

Zuza · 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 · Post by **jambon_vn** » Thu Oct 14, 2004 4:56 am

Check this post http://online-judge.uva.es/board/viewto ... e35982d203

masumasu · 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;
}

BenderBendingRodriguez · 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

UFP2161 · 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..

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

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

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;
}

shamim · 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.

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

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

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; 
}

shamim · 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.

lazenca · 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()   */
}

Iwashere · 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

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

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

first of all, thanks....

I noticed that my code has many fault...oooooo......

lazenca · 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;
}

UVa OJ Board

108 - Maximum Sum

Problem in 108 with my solution ...plzzzzzzzz help

108 - Maximum Sum - Time Limit Exceeded

#108 WA plz help me @_@

hm...=_=