108 - Maximum Sum

[mido]

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]

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]

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.

[shamim]

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]

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]

[hectorzeta]

Hi

I

[hectorzeta]

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]

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]

Go to related topics in this forum!!!

Search the board! http://acm.uva.es/board/search.php

[xbeanx]

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]

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]

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]

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]

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

[shamim]

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.