108 - Maximum Sum

[ulin]

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]

Sorry

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

Best Regards!

[Stas]

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

[mishu]

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]

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]

but your code outputs
[c]
enter the sieze of array:
enter the elements:
arr[0][0] arr[0][1] arr[0][2] arr[0][3] arr[1][0] arr[1][1] arr[1][2] arr[1][3] arr[2][0] arr[2][1] arr[2][2] arr[2][3] arr[3][0] arr[3][1] arr[3][2] arr[3][3] max value is15
[/c]

Can you see the difference.

[mishu]

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]

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

[jagadish]

there are already many threads on this problem - you can use the 'search' function to find what u want before posting

[wolf]

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.

[vladrac]

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[0][0];
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];

return total;
}

[/cpp]

[efr_shovo]

Please Give ME Some Critical InPut OutPut For Prob-108.Please Help

[shamim]

try this:
[cpp]
4
-1 -2 -3 -4
-5 -6 -7 -8
-9 -10 -11 -12
-13 -14 -15 -16
[/cpp]

[efr_shovo]

But Friend Waht is the out put

[jambon_vn]

How to get the answer for one-dimension with O(n). I can't find any.

[dumb dan]

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)