## 108 - Maximum Sum

Moderator: Board moderators

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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.

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
I got your idea. Thanks a lot.

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
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

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

### Problem in 108 with my solution ...plzzzzzzzz help

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
New poster
Posts: 13
Joined: Wed Sep 08, 2004 10:54 am

### 108 - Maximum Sum - Time Limit Exceeded

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.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
naive O(N^6) is too slow.. though maybe if you memoize it some, it might be fast enough..

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

### #108 WA plz help me @_@

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;
}
``````
I see the red...
I saw the rain..

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

### hm...=_=

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;
}
``````
I see the red...
I saw the rain..

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:
Thanks!
I modified my code...but still WA..
what is missing things?

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
Input:

Code: Select all

``````4
-100 4 4 -100
-100 4 4 -100
-100 4 4 -100
-100 4 4 -100``````

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

lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:
first of all, thanks....

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

lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:
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..