## 108 - Maximum Sum

Moderator: Board moderators

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)
I don't get your complexity n^3
There may be both positive and negative integers.
Is there finally algorithm O(n^3) for this problem?

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)
Sorry

I didn't realize that there is possible to compute answer in O(n) for one-dimensional problem.

Best Regards!

Stas
New poster
Posts: 5
Joined: Sat Jul 03, 2004 5:15 pm
Location: Kyrgyzstan
Contact:

### huh

I solved this problem in using n^4 alhorytm with some optimization. 8sec :) pascal

mishu
New poster
Posts: 4
Joined: Thu Sep 02, 2004 2:45 am

### time exceeds in 108 problem

hey this is my code please tell me why i get time exceed in my code and how can i check on my pc whether time exceed has happen or not and what should i do for time to not exceed
below is my code (it works fine)

#include<iostream.h>
#include<stdlib.h>
void main()
{
int n1,i,j,c,m,q,n,max=0,p,l,k;
cout<<"enter the sieze of array: ";
cin>>n1;
cout<<endl;
int **arr = (int **)malloc(n1*sizeof(int *));
for(i=0 ;i < n1; i++)
arr = (int *)malloc(n1*sizeof (int));
cout<<"enter the elements: "<<endl;
for(i = 0 ; i < n1 ; i++)
for(j = 0 ; j < n1 ; j++)
{
cout<<"arr["<<i<<"]["<<j<<"]"<<" ";
cin>>arr[j];
if(max < arr[j])
max = arr[j];
}

for(c = 0; c < n1-1; c++)
{
for(i = 0; i < n1-1 ;i++)
{
for(m = n1-1 ; m > c ; m--)
{
q = n1;
while(q > i+1)
{
n = 0;
for(j=c ; j<=m; j++)
n = n+arr[j];
for(k = i+1 ; k < q; k++)
n = n+arr[k][j-1];
for(l=j-2;l>=c;l--)
n=n+arr[k-1][l];
for(p=k-2;p>i;p--)
n=n+arr[p][c];
if(max<n)
max = n;
q--;
}
}
}
}
cout<<"max value is"<<max;
}

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
From what it looks, your algorithm seems to have a complexity of something like O(n^5) or O(n^6) and it will not pass the time limit. You can solve this problem using O(n^4) or even O(n^3) using dynamic programming or something of that sort. And you are not allowed to print comments in your source code. For the sample input the output should be

[c]
15
[/c]

[c]
enter the sieze of array:
enter the elements:
arr arr arr arr arr arr arr arr arr arr arr arr arr arr arr arr max value is15
[/c]

Can you see the difference. mishu
New poster
Posts: 4
Joined: Thu Sep 02, 2004 2:45 am

### help on 108

hey can u please suggest me some prog which uses o^4 or O^3 algo like what u r saying using dynamic kinda of solution please give me example of what u mean by all that type of algo its will be very thanful of u

mishu
New poster
Posts: 4
Joined: Thu Sep 02, 2004 2:45 am

### 108 problem how to do it dynamically

hey i want to know how can i find whether my algo is O^6 or any other and also please tell me how can i solve 108 problem dynamically i have it solved by method that is using O^5 algo (some said) and he said use dynamic prog though i have created array using dyanmic prog now how can i even calulate the smallest rectangle also by dynamic programming please help

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
there are already many threads on this problem - you can use the 'search' function to find what u want before posting

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Hi mishu!
U can try that : After reading the input data,process throught all possible combinations, but don't count the whole sum all the time. You can add a column/row of integers to existing matrix. Also you can substract the integers at the same way (if needed, I don't remember 108 well). I did it like this and fit in time limit (my prog run ~0.1 sec) Hope it helps

P.S. Sorry for my horrible english, I hope you'll understand what I mean.

New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

### 108 works but takes too long! anyhelp

This code works! But takes too long!

Any suggestions Plz!

[cpp]
#include <stdio.h>
#include <malloc.h>

int n=1,ROWS,COLS;
int **array;
int sum_line(int **array1,int *ind,int *ii,int *jj);

int main(void){
int i,j,n,x,y,xi,xj,ni,nj,sum=0,sumq=0,sumtotal=0,val;

sumtotal=0;
scanf("%d",&n);
if(n!=0)
{
ROWS=n;
COLS=n;

int **array = (int **)malloc(n*sizeof(int *));
for(i=0 ;i < n; i++)
array = (int *)malloc(n*sizeof (int));

for(i = 0 ; i < n ; i++) for(j = 0 ; j < n ; j++)
{
scanf("%d",&val);
array[j]=val;
}

x=0;
xi=0;
xj=COLS;
sumq=0;
sumtotal=array;
int interacoes=0;
for(xj=COLS;xj>-1;xj--)
{
for(nj=0;nj<xj;nj++)
{

for(ni=0;ni<ROWS;ni++)
{
sumq=0;

for(x=ni;x<ROWS;x++)
{
sum=sum_line(array,&x,&nj,&xj);
sumq+=sum;
if(sumtotal<sumq) sumtotal=sumq;
}
}
}
}

}
printf("%d",sumtotal);

return 0;

}

int sum_line(int **array1,int *ind,int *ii,int *jj)
{
int total=0,i,j,xi,xj;
for( j=*ii;j<*jj;j++) total+=array1[*ind][j];

}

[/cpp]

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
try this:
[cpp]
4
-1 -2 -3 -4
-5 -6 -7 -8
-9 -10 -11 -12
-13 -14 -15 -16
[/cpp]

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### What is the output

But Friend Waht is the out put

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am
How to get the answer for one-dimension with O(n). I can't find any.

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
For a one-dimensional problem: [x1 x2 x3 ... xn]
You need to keep track of partial sums. For example
make a new array [s1 s2 s3 .... sn] where:
s1 = x1
s2 = max(x2, s1+x2)
s3 = max(x3, s2+x3)
...
sn = max(xn, s(n-1)+xn)
max_sum=max(s1, s2, s3, ..., sn)