108 - Maximum Sum

[Iwashere]

nope it's wrong

Code: Select all

4
1 1 1 1
1 1 1 1
1 1 1 -1
1 1 1 1

output should be 14, not 15

Read some other threads on this problem to find the algo to use for it.

[lazenca]

oops...

I tried to O(N^2)...hm..

Code: Select all

#include <iostream.h>
#include <limits.h>



void   init_array2(int   array[100]);

void main()
{
	int   N;
	int   i, x, array[100] = {0}, limits, col;
	int   in_data, sub_cumulative, max_sum;
	int   *table;

	cin >> N;
	
	limits = N*N;
	table = new int[limits];

	for (i = 0;   i < limits;   i++)
		cin >> table[i];


	max_sum = INT_MIN;
	sub_cumulative = 0;

	for (i = 0;   i < limits;   i++)   {

		for (x = i, col = i % N;   x < limits;   )   {
		
			in_data = table[x];
			
			array[col] = (in_data > array[col] + sub_cumulative + in_data) ?
						in_data :
						array[col] + sub_cumulative + in_data;
			
			sub_cumulative = (in_data > sub_cumulative + in_data) ?
								in_data:
								sub_cumulative + in_data;

			if (array[col] > max_sum)   {
				max_sum = array[col];
			}
			
		
			if (++x % N == 0)   {    /*   end of row   */
				x += i % N;           /*   move to next row   */
				sub_cumulative = 0;
				col = i % N;         /*   start column   */
			}
			else
				col++;
			
		}   /*   end of one sub rectangle   */

		init_array2(array);

	}   /*   end of otter for()   */

	cout << max_sum << endl;
}


void   init_array2(int   array[100])
{
	for (int i = 0; i < 100; i++)
		array[i] = 0;
}

[CodeMaker]

Did you got Accepted on this problem lazenca?

[lazenca]

nope..I still got WA..hm...

[CodeMaker]

Do you think you can solve this in O(n^2), because I thought only O(n^3) exists. have you got a profe on this O(n^2) theorem?

[nnahas]

Do you think you can solve this in O(n^2), because I thought only O(n^3) exists. have you got a profe on this O(n^2) theorem?

I really, really don't think there's an easy O(N^2) algo for this algo (and by easy I mean necessitating less than a lifetime of research) . It's been an open problem for 20 years or more. This problem is known as the maximum subarray problem in the literature.
I think the best running time known for this problem is something like O(N^3/ sqrt(lgn)).
To find scientific papers written about this problem , make a search on Google on
"maximum subarray" . the O(N^3) algorithm is known as the "Kadane algorithm" , named after its inventor.

If you're interested see this paper.
nz.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf

[lazenca]

Thanks for advice...
The paper is very helpful to me..

This problem is much complicate than I thought..

I'll try hard to accept this..

[lazenca]

I got AC...
I very much appreciate your helps.

But It's too slow... hm...

I'll try to make it faster...

[CodeMaker]

Good, but did you use O(n^3) or O(n^4)?

[lazenca]

maybe, I use O(N^3)...

[PerHagen]

now?
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main(void)
{int arreglo[10][10],n,i,j;long suma,max=-12700;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&arreglo[j]);

for (int ancho=1;ancho<=n;ancho++)
for (int largo=1;largo<=n;largo++)
for ( i=0;i<=n-ancho;i++)
for ( j=0;j<=n-largo;j++)
{
for( int i2=0;i2<n;i2++ )
for( int j2=0;j2<n;j2++)
{
suma=0;
for (int i1=i;i1<=i2;i1++)
{
for (int j1=j;j1<=j2;j1++)
{
suma+=arreglo[i1][j1];
}
}

if ( suma >=max ) max=suma;
}
}
cout << max;
}
is W.A ...i don't understand
bye

[nnahas]

1) You have a very nice array overflow. the array can be 100 by 100 and you declared it 10 by 10
2)Your algo as far as I can judge is O(N^6), and that's too slow . so even if you correct all your bugs , you will get a Time Limit Exceeded error.
These are the errors I saw, maybe there are others.

There is a lot of discussion concerning this problem on this message board. Use the search feature to find the previous messages about this problem as they might help you

[PerHagen]

opps you win!

you have I/O of 108 ?
much for is slow ...mmmm yes you win

bye thx

[ImLazy]

Use this algorithm:
First consider this problem: In an array, find the sub-array of the maximum sum.
Think about these points:
1. If a sub-array has maximum sum, it must begins with a positive number. Because if it begins with a negative number, it will only make it smaller.
2. If a sub-array has maximum sum, it must begins with a sub-array of positive sum. The reason is the same as above.
So we get this algorithm:

Code: Select all

Suppose the array is: A1,A2,A3,A4 ... An
1.MaxMax <-- 0
2. For i=1,2...n
  2.1. If Ai<=0 then: goto 2. (We don't want to begin with a negative)
  2.2. (Now Ai is positive, so let it be the beginning of this sub-array)
       sum <-- Ai ; max <-- Ai
  3.3. For j=i+1,i+2...
    3.3.1. sum <-- sum+Ai
    3.3.2. If sum>max then: max <-- sum
    3.3.3. Else if sum<=0 then:
             (this sub-array can't have max sum, so give ti up.)
      3.3.3.1. If max>MaxMax then: MaxMax <-- max
      3.3.3.2. goto 2.(Try to begin with another positive)

Thus, we can get the sub-array of biggest sum. And it is not difficult to extend this algorithm to 2-dimension. Hope it helps.

[PerHagen]

thx ... my code is O(n!) ..jaja .. your code is very good
bye