## 108 - Maximum Sum

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 108 again

What's wrong with this...?...:

[cpp]
#include <iostream.h>

void main()
{
long dim;
while (!cin.eof() && cin>>dim && !cin.fail())
{
long list;
long list_sum;
long sum=0;
long i,j;
long max=-127*1000;
for (j=0;j<dim;j++)
{
cin>>list[j];
sum+=list[j];
list_sum[j]=sum;
max = list[j]>max ? list[j] : max;
max = list_sum[j]>max ? list_sum[j] : max;
}
for (i=1;i<dim;i++)
{
for (j=0;j<dim;j++)
{
cin>>list[j];
list_sum[j]=0;
max = list[j]> max ? list[j] : max;
list_sum[j]+=list_sum[i-1][j];
int k;
for (k=j;k>=0;k--)
list_sum[j]+=list[k];
max = list_sum[j]>max ? list_sum[j] : max;
}
}
for (i=1;i<dim;i++)
{
for (j=1;j<dim;j++)
{
int k;
for (k=i-1;k>=0;k--)
max = list_sum[j]-list_sum[k][j]>max ? list_sum[i][j]-list_sum[k][j] :
max;
for (k=j-1;k>=0;k--)
max = list_sum[i][j]-list_sum[i][k]>max ? list_sum[i][j]-list_sum[i][k] :
max;
}
}
cout<<max<<endl;
}
}
[/cpp]

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
I got AC so need to bother...for those who want to know, this code has just a 2-level for loop left for the solution to get AC...good luck.. Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

### Prob 108. What is the O(n^3) algo? who can explain it to me?

Hello,

I tried to solve prob 108, and I found the O(n^6) algo. (Brute Force)
But it would get TLE.

I heard there exists O(n^3) algo. I want to know it.

There general idea is DP. We can use one dimension result.
I know how to get maximum sum from 1 dim, but how it can be
applicable to 2 dim problem?

plz explain it to me in detail.

Thx.
Sorry for my poor English.

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

### cumulative

Ok,

You need to create another two dim array to hold the cumulative sum for each column.
e.g

for
1 2 3
3 4 6
2 4 5

cumulative array is (->indicates row number)
0 0 0 ->1
1 2 3 -> 2
4 6 9 -> 3
6 10 14 -> 4

using this cum. array use brute force to obtain a single dimensional array of size n; here is how it should be done

row 4 - row 3 gives
2 4 5, now use your method for one dim on this one dim array. this may be potential max, so you must store it.

Then obtain row 4 - row 2 , row 4 - row 1

The next step is to do it with row 3 - row 2 , row 3 - row 1 and so on.
The maximum sum will be the max value of the above procedure.

This works if all numbers are >0, for all negative, you must make an extra check. I hope this will be of some help. Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

### Thanks a lot!

I got AC at once with your comment! It helps me a lot!

Thanks again..

And, is there any possibilities to improve this code?
I seldom care about the CPU time, but, this code is very slow.
(The CPU time was 0.050.. but there are many 0.20 - 0.30 rankers..
I heard that O(N^3) algo is the most efficent way to solve this problem.)

This is my full code :
[cpp]
#include <cstdio>
#include <algorithm>

#define MAX_N 100

using namespace std;

int main()
{
int N, Max = 0;
int Cumulate[MAX_N + 1] = {0}, Table[MAX_N + 1][MAX_N + 1] = {0};

scanf("%d", &N);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
scanf("%d", &Table[j]);
Table[j] += Table[j];
}

for (int j = 1; j < i; j++) {
for (int k = 1; k <= N; k++) {
Cumulate[k] = Table[k] - Table[j][k];

Cumulate[k] = max(Cumulate[k - 1] + Cumulate[k],
Cumulate[k]);

if (Cumulate[k] > Max)
Max = Cumulate[k];
}
}
}

printf("%d\n", Max);

return 0;
}

[/cpp]
Sorry for my poor English.

hectorzeta
New poster
Posts: 4
Joined: Mon Jun 23, 2003 1:54 am

### Problem 108 (java) Could you help me? I got WA

Hi

I

hectorzeta
New poster
Posts: 4
Joined: Mon Jun 23, 2003 1:54 am

### I have the same problem??

I resolve the problem but the online judge reported me Time Exceeded. And firts I resolve the problem in java and I got WA. With the same algorithm
[c]
// @JUDGE_ID: 32852WA 108 c++
#include <stdio.h>
#include <iomanip.h>

int sumaCuadro(int arr[], int ide, int jde, int ia, int ja){
int suma = 0;
for(int i = ide; i <= ia; i++){
for(int j = jde; j <= ja; j++){
suma += arr[j];
}
}
return suma;
}

void main(void){

int maxSum = 0;
int arr = {{0}};
int num = 0;
cin>>num;
if (num <= 100 && num >= 1){
for(int i = 0; i < num ; i++){
for(int j = 0; j < num ; j++){
cin>>arr[j];

if(i == 0 && j == 0)
maxSum = arr[j];
maxSum = arr[j] > maxSum ? arr[j] : maxSum;
}
}

for(int k = 0; k < num; k++){
for(int l = 0; l < num; l++){
for(int i = k; i < num; i++){
for(int j = l; j < num; j++){
}
}
}
}
cout<<(maxSum);

}
}
[/c]

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
to hectorzeta and ozton...

your algorithm very slow for this problem. you cannot use O(n^6) or O(n^7) if n = 100 you will get TLE. you must optimize your algo in O(n^3) or O(n^4).

try to find them. Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Go to related topics in this forum!!!

Search the board! http://acm.uva.es/board/search.php
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm

### Any more test cases for 108?

Hey guys. My program seems to work for the sample input and a couple of extra cases posted around here.

However, when I submit I am getting a WA. Does anyone have any other test cases I can try, or can someone suggest some "trickery" cases that I may not be checking for?

My code is much like many examples posted here that work:
[java]
import java.io.IOException;
import java.util.StringTokenizer;

class Main {
static int n;
static int[][] matrix;

public static void main(String[] args) throws IOException {
matrix = new int[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) {
matrix[j] = Integer.parseInt(st.nextToken());
}
solve();
}

static void solve() {
int[] best = new int[n];
int[][] sums = new int[n][n];
for(int j = 0; j < n; j++)
for(int i = 0; i < n; i++)
sums[j] = (i==0) ? matrix[j] : sums[i-1][j]+matrix[j];

int maximum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++) {
best[k] = (i==j) ? sums[k] : sums[k]-sums[j][k];
if(k>0 && best[k]+best[k-1]>best[k])
best[k] = best[k]+best[k-1];
if(best[k] > maximum) maximum = best[k];
}
System.out.println(maximum);
}

static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
while(lg < maxLg) {
if(car<0 || car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg).trim();
}
}
[/java]

Thanks for any help, guys.

PS: sorry about the wrapped lines (makes it a little harder to read)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Damnit!

I was staring at my code for over 4 hours. And wouldn't you know 10 minutes after I write this message I find the bug.

For those of you who can't see it: change

for(int j = 0; j < n; j++)
to
for(int j = 0; j < i; j++)

in a part of the code.

toren
New poster
Posts: 5
Joined: Thu Aug 21, 2003 3:39 pm
Location: Bergen, Norway

### 108

I keep noticing that people claim there is an O(n^3) algorithm
for solving problem 108. I cannot see how that can be when there
are (n(n+1)/2)^2 = O(n^4) possible rectangles on an nxn board.
Even if you knew all the sums of the rectangles and didn't need to compute them,
you still had to iterate through all of the O(n^4) sums of rectangles to find the maximum.

Anyone got an explanation?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
This O(n^3) algorithm boggled me for a while too.

There is a description of the O(n) algorithm for the maximum sum of a vector (i.e. just one of the rows of the matrix) in Programming Pearls by Bentley.

I don't want to spoil anything. You can either find that book and read the relevant section, or think of how you can solve the one dimensional problem in O(n), but I guess I can give you this one hint: Consider what happens when you have a running sum and when that sum is negative/zero/positive.

This can then be extended for the two dimensional case.

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

### 108

Can't find any clue how to implement a O(n^3) algorithm for this problem.
Can anybody help?
novice programmer

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
You need to create a two dim array to hold the cumulative sum for each column.
e.g

for
1 2 3
3 4 6
2 4 5

cumulative array is (->indicates row number)
0 0 0 ->1
1 2 3 -> 2
4 6 9 -> 3
6 10 14 -> 4

using this cum. array use brute force to obtain a single dimensional array of size n; here is how it should be done

row 4 - row 3 gives
2 4 5, now it is easy to obtain the maximum for this one dimensional array. this may be potential max, so you must store it.

Then obtain row 4 - row 2 , row 4 - row 1

The next step is to do it with row 3 - row 2 , row 3 - row 1 and so on.
The maximum sum will be the max value of the above procedure.

This works if all numbers are >0, for all negative, you must make an extra check. 