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
mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

108 again

Post by mido » Sun Feb 16, 2003 8:34 pm

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

[cpp]
#include <iostream.h>

void main()
{
long dim;
while (!cin.eof() && cin>>dim && !cin.fail())
{
long list[110][110];
long list_sum[110][110];
long sum=0;
long i,j;
long max=-127*1000;
for (j=0;j<dim;j++)
{
cin>>list[0][j];
sum+=list[0][j];
list_sum[0][j]=sum;
max = list[0][j]>max ? list[0][j] : max;
max = list_sum[0][j]>max ? list_sum[0][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

Post by mido » Mon Feb 17, 2003 12:15 am

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

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?

Post by Diskerr » Sun May 04, 2003 8:16 am

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.

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

cumulative

Post by shamim » Sun May 04, 2003 11:14 am

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!

Post by Diskerr » Sun May 04, 2003 3:02 pm

I got AC at once with your comment! :D

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

Post by hectorzeta » Wed Jun 25, 2003 12:55 am

Hi

I

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

I have the same problem??

Post by hectorzeta » Wed Jun 25, 2003 2:29 am

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[][100], 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[100][100] = {{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++){
maxSum = sumaCuadro(arr,k,l,i,j) > maxSum ? sumaCuadro(arr,k,l,i,j) : maxSum;
}
}
}
}
cout<<(maxSum);

}
}
[/c]

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Wed Jun 25, 2003 6:30 am

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

Post by Observer » Wed Jun 25, 2003 6:35 am

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
Location: Newfoundland, Canada (St. John's)

Any more test cases for 108?

Post by xbeanx » Wed Aug 06, 2003 8:20 pm

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 {
n = Integer.parseInt(readLine(16));
matrix = new int[n][n];
StringTokenizer st = new StringTokenizer(readLine(128));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) {
if(!st.hasMoreTokens()) st = new StringTokenizer(readLine(128));
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) {
car = System.in.read();
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
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Wed Aug 06, 2003 9:44 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

Post by toren » Wed May 26, 2004 3:33 pm

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?

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

Post by UFP2161 » Wed May 26, 2004 9:13 pm

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

Post by samueljj » Sat Jun 12, 2004 7:49 am

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

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

Post by shamim » Sat Jun 12, 2004 8:13 am

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

Post Reply

Return to “Volume 1 (100-199)”