108  Maximum Sum
Moderator: Board moderators
How to solve problem 108??
I used O(N^4) algorithm and got AC.
Is there any faster DP algorithm?
Is there any faster DP algorithm?
Sorry for my bad English...
OTL
frustrate
OTL
frustrate

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:

 New poster
 Posts: 44
 Joined: Tue Jun 06, 2006 6:44 pm
 Location: Nova Scotia, Canada
 Contact:
108 AC
Here's my simple solution too 108, it's roughly O((N^4)/4), runs in 1.1~ seconds
I would describe it as "eligant brute force", it checks all possible rectangles, but it accumulates sums to save it from having too sum each rectangle seperatley, thus saving it from being O(N^6)
Edited by : Jan
Code: Select all
Code Removed ..
Edited by : Jan
 Chris Adams

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

 New poster
 Posts: 44
 Joined: Tue Jun 06, 2006 6:44 pm
 Location: Nova Scotia, Canada
 Contact:

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
108  MaximumRectangleSum  WA  Any idea
Where can I view the input for which my solution failed ? Any insight would be helpful.
I assumed positive integer (N) to be any number >=0 . and I tested for corner cases like all negatives, zeros and stuff like tht. I used dp for this.
Thanks
Code: Select all
/* Maximum sum */
#include <iostream>
#include <vector>
using namespace std;
class MaximumRectangleSum
{
int a[100][100];
int b[100][100];
int max, sum;
int n;
public:
void Init();
int ComputeMaximumSum(void);
bool IsValidIndex(int i, int j);
};
bool MaximumRectangleSum::IsValidIndex(int i, int j)
{
if(i >= 0 && i < n && j >= 0 && j < n) return true;
return false;
}
void MaximumRectangleSum::Init()
{
int leftabove = 0, upabove = 0, diagonalabove = 0;
while(cin >> this>n)
{
max = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
leftabove = 0, upabove = 0, diagonalabove = 0;
b[i][j] = 0;
cin >> this>a[i][j];
if(IsValidIndex(i, j1))
leftabove = b[i][j1];
if(IsValidIndex(i1, j))
upabove = b[i1][j];
if(IsValidIndex(i1, j1))
diagonalabove = b[i1][j1];
b[i][j] = leftabove + upabove  diagonalabove + a[i][j];
if(b[i][j] > max) max = b[i][j];
}
}
cout << ComputeMaximumSum() << endl;
}
}
int MaximumRectangleSum::ComputeMaximumSum()
{
for(int w = 1; w < n; ++w)
{
for(int x = 0; x < n; ++x)
{
for(int y = 1; y < n; ++y)
{
for(int z = x; z < n; ++z)
{
sum = b[y][z];
if(IsValidIndex(y, x1))
sum = b[y][x1];
if(IsValidIndex(w1, z))
sum = b[w1][z];
if(IsValidIndex(w1, x1))
sum += b[w1][x1];
if(sum > max) max = sum;
}
}
}
}
return max;
}
void Start1()
{
//int a[4][4] = {
// {0, 2, 7, 0},
// {9, 2, 6, 2},
// {4, 1, 4, 1},
// {1, 8, 0, 2}
//};
//int n = 4;
MaximumRectangleSum p;
//p.Init(a, n);
p.Init();
}
//TODO
int main()
{
Start1();
return 0;
}
Thanks