I've found task 108 [ http://acm.uva.es/p/v1/108.html ] but there is
nothing except task statement.
I have written a program that solves this problem (see listing below)
but It has complexity = O(N^4).
Please look at my program it's quite simple to understand and prints
debug output
(see at the bottom of this post). It also counts number of iterations
performed.
For 4x4 matrix, from task sample input, it performs 100 iterations.
It's very likely that my algorithm differs from your (that works for
O(n^3) ).
Is it required for your algorithm that matrix is square? My algorithm
works for any matrix N x M,
can it make the difference?
Listing: ---------------
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <exception>
#include <stdexcept>
using namespace std;
class Range {
public:
int x0, y0, x1, y1;
int width () const { return y1 - y0; }
int height() const { return x1 - x0; }
explicit Range(int px0=0, int py0=0, int px1=0, int py1=0)
: x0(px0), y0(py0), x1(px1), y1(py1) {}
friend ostream & operator << (ostream & out, const Range & range) {
return out<<"["<<range.x0<<", "<<range.y0<<"; "<<range.x1<<",
"<<range.y1<<"]";
}
};
/**
* Splits range on smaller pices, if possible, or returns it self.
*/
vector<Range> split(const Range & r) {
vector<Range> result;
result.reserve(4);
if (r.width() == 1 && r.height() == 1) {
result.push_back(r);
} else if (r.width() > 1 && r.height() == 1) {
result.push_back(Range(r.x0, r.y0, r.x0 + 1, r.y0 + r.width() -
1));
result.push_back(Range(r.x0, r.y0 + r.width() - 1, r.x0 + 1,
r.y0 +
r.width()));
} else if (r.height() > 1 && r.width() == 1) {
result.push_back(Range(r.x0, r.y0, r.x0 + r.height() - 1, r.y0 +
1));
result.push_back(Range(r.x0 + r.height() - 1, r.y0, r.x0 +
r.height(), r.y0 + 1));
} else {
result.push_back(Range(r.x0, r.y0, r.x0 + r.height() - 1, r.y0 +
r.width() - 1));
result.push_back(Range(r.x0 + r.height() - 1, r.y0, r.x0 +
r.height(), r.y0 + r.width() - 1));
result.push_back(Range(r.x0, r.y0 + r.width() - 1, r.x0 +
r.height()
- 1, r.y0 + r.width()));
result.push_back(Range(r.x0 + r.height() - 1, r.y0 + r.width()
- 1,
r.x0 + r.height(), r.y0 + r.width()));
}
return result;
}
template <class Value_>
class Matrix {
public:
int getN() const { return _n; }
int getM() const { return _m; }
vector<Value_> & operator[] (int index) {
return _rows[index];
}
const vector<Value_> & operator[] (int index) const {
return _rows[index];
}
Matrix subMatrix(const Range & r) {
Matrix result(r.height(), r.width());
for (int i = 0; i < result.getN(); i++ ) {
for (int j = 0; j < result.getM(); j++ ) {
result[i][j] = _rows[r.x0 + i][r.y0 + j];
}
}
return result;
}
/*
* Create matrix with n rows and m columns
*/
explicit Matrix(int n=0, int m=0) : _n(n), _m(m), _rows(n) {
for (int i = 0; i < n; i++ ) {
_rows[i] = vector<Value_>(m);
}
}
/*
* Create matrix with n rows and m columns filled by value defValue
*/
Matrix(int n, int m, const Value_ & defValue) : _n(n), _m(m),
_rows(n) {
for (int i = 0; i < n; i++ ) {
_rows[i].reserve(m);
fill_n(back_inserter(_rows[i]), m, defValue);
}
}
friend ostream& operator << (ostream & out, const Matrix & m) {
out<<m.getN()<<" "<<m.getM()<<endl;
for (int i = 0; i < m.getN(); i++ ) {
for (int j = 0; j < m.getM(); j++ ) {
out<<m[i][j]<<" ";
}
out<<"\n";
}
return out;
}
private:
int _n, _m;
vector<vector<Value_> > _rows;
};
/*
* Implements dynamic programming approach.
*/
class DPSolver {
public:
void solve(Range & result, int & max) {
max = numeric_limits<int>::min();
for (int h = 1; h <= height(); h++ ) {
for (int w = 1; w <= width(); w++ ) { // Start with
width = 2
cout<<"-debug- Checking matrices:
"<<h<<"x"<<w<<endl;
for (int y0 = 0; y0 <= width() - w; y0++ ) {
for (int x0 = 0; x0 <= height() - h;
x0++ ) {
Range r(x0, y0, x0 + h, y0 + w);
vector<Range> sr = split(r);
int sum = 0;
for (size_t i = 0; i <
sr.size(); i++ ) {
sum+= sums(sr[i]);
}
sums(r) = sum;
if (sum > max) {
max = sum;
result = r;
}
_count++;
cout<<"-debug-\t range:
"<<r<<", sum: "<<sum<<endl;
}
}
}
}
}
int getCount() const { return _count; }
DPSolver(const Matrix<int> & matrix) : _count(0), _matrix(matrix),
_sums(matrix.getN(), matrix.getM(),
Matrix<int>( matrix.getN(), matrix.getM(), 0)) {
for (int x0 = 0; x0 < height(); x0++ ) {
for (int y0 = 0; y0 < width(); y0++ ) {
_sums[x0][y0][0][0] = _matrix[x0][y0];
}
}
}
private:
int width () const { return _matrix.getM(); }
int height() const { return _matrix.getN(); }
int & sums(const Range & r) {
return _sums[r.x0][r.y0][r.width() - 1][r.height() - 1];
}
private:
int _count;
const Matrix<int> & _matrix;
Matrix<Matrix<int> > _sums;
};
int main() {
Matrix<int> m(4, 4, 0);
m[0][0] = 0; m[0][1] = -2; m[0][2] = -7; m[0][3] = 0;
m[1][0] = 9; m[1][1] = 2; m[1][2] = -6; m[1][3] = 2;
m[2][0] = -4; m[2][1] = 1; m[2][2] = -4; m[2][3] = 1;
m[3][0] = -1; m[3][1] = 8; m[3][2] = 0; m[3][3] = -2;
DPSolver dps(m);
Range r;
int sum;
dps.solve(r, sum);
cout<<endl;
cout<<"SumOpCount: "<<dps.getCount()<<endl;
cout<<"Range: "<<r<<", sum: "<<sum<<endl;
cout<<"Matrix: "<<m.subMatrix(r)<<endl;
return 0;
}
--- Program output:
-debug- Checking matrices: 1x1
-debug- range: [0, 0; 1, 1], sum: 0
-debug- range: [1, 0; 2, 1], sum: 9
-debug- range: [2, 0; 3, 1], sum: -4
-debug- range: [3, 0; 4, 1], sum: -1
-debug- range: [0, 1; 1, 2], sum: -2
-debug- range: [1, 1; 2, 2], sum: 2
-debug- range: [2, 1; 3, 2], sum: 1
-debug- range: [3, 1; 4, 2], sum: 8
-debug- range: [0, 2; 1, 3], sum: -7
-debug- range: [1, 2; 2, 3], sum: -6
-debug- range: [2, 2; 3, 3], sum: -4
-debug- range: [3, 2; 4, 3], sum: 0
-debug- range: [0, 3; 1, 4], sum: 0
-debug- range: [1, 3; 2, 4], sum: 2
-debug- range: [2, 3; 3, 4], sum: 1
-debug- range: [3, 3; 4, 4], sum: -2
-debug- Checking matrices: 1x2
-debug- range: [0, 0; 1, 2], sum: -2
-debug- range: [1, 0; 2, 2], sum: 11
-debug- range: [2, 0; 3, 2], sum: -3
-debug- range: [3, 0; 4, 2], sum: 7
-debug- range: [0, 1; 1, 3], sum: -9
-debug- range: [1, 1; 2, 3], sum: -4
-debug- range: [2, 1; 3, 3], sum: -3
-debug- range: [3, 1; 4, 3], sum: 8
-debug- range: [0, 2; 1, 4], sum: -7
-debug- range: [1, 2; 2, 4], sum: -4
-debug- range: [2, 2; 3, 4], sum: -3
-debug- range: [3, 2; 4, 4], sum: -2
-debug- Checking matrices: 1x3
-debug- range: [0, 0; 1, 3], sum: -9
-debug- range: [1, 0; 2, 3], sum: 5
-debug- range: [2, 0; 3, 3], sum: -7
-debug- range: [3, 0; 4, 3], sum: 7
-debug- range: [0, 1; 1, 4], sum: -9
-debug- range: [1, 1; 2, 4], sum: -2
-debug- range: [2, 1; 3, 4], sum: -2
-debug- range: [3, 1; 4, 4], sum: 6
-debug- Checking matrices: 1x4
-debug- range: [0, 0; 1, 4], sum: -9
-debug- range: [1, 0; 2, 4], sum: 7
-debug- range: [2, 0; 3, 4], sum: -6
-debug- range: [3, 0; 4, 4], sum: 5
-debug- Checking matrices: 2x1
-debug- range: [0, 0; 2, 1], sum: 9
-debug- range: [1, 0; 3, 1], sum: 5
-debug- range: [2, 0; 4, 1], sum: -5
-debug- range: [0, 1; 2, 2], sum: 0
-debug- range: [1, 1; 3, 2], sum: 3
-debug- range: [2, 1; 4, 2], sum: 9
-debug- range: [0, 2; 2, 3], sum: -13
-debug- range: [1, 2; 3, 3], sum: -10
-debug- range: [2, 2; 4, 3], sum: -4
-debug- range: [0, 3; 2, 4], sum: 2
-debug- range: [1, 3; 3, 4], sum: 3
-debug- range: [2, 3; 4, 4], sum: -1
-debug- Checking matrices: 2x2
-debug- range: [0, 0; 2, 2], sum: 9
-debug- range: [1, 0; 3, 2], sum: 8
-debug- range: [2, 0; 4, 2], sum: 4
-debug- range: [0, 1; 2, 3], sum: -13
-debug- range: [1, 1; 3, 3], sum: -7
-debug- range: [2, 1; 4, 3], sum: 5
-debug- range: [0, 2; 2, 4], sum: -11
-debug- range: [1, 2; 3, 4], sum: -7
-debug- range: [2, 2; 4, 4], sum: -5
-debug- Checking matrices: 2x3
-debug- range: [0, 0; 2, 3], sum: -4
-debug- range: [1, 0; 3, 3], sum: -2
-debug- range: [2, 0; 4, 3], sum: 0
-debug- range: [0, 1; 2, 4], sum: -11
-debug- range: [1, 1; 3, 4], sum: -4
-debug- range: [2, 1; 4, 4], sum: 4
-debug- Checking matrices: 2x4
-debug- range: [0, 0; 2, 4], sum: -2
-debug- range: [1, 0; 3, 4], sum: 1
-debug- range: [2, 0; 4, 4], sum: -1
-debug- Checking matrices: 3x1
-debug- range: [0, 0; 3, 1], sum: 5
-debug- range: [1, 0; 4, 1], sum: 4
-debug- range: [0, 1; 3, 2], sum: 1
-debug- range: [1, 1; 4, 2], sum: 11
-debug- range: [0, 2; 3, 3], sum: -17
-debug- range: [1, 2; 4, 3], sum: -10
-debug- range: [0, 3; 3, 4], sum: 3
-debug- range: [1, 3; 4, 4], sum: 1
-debug- Checking matrices: 3x2
-debug- range: [0, 0; 3, 2], sum: 6
-debug- range: [1, 0; 4, 2], sum: 15
-debug- range: [0, 1; 3, 3], sum: -16
-debug- range: [1, 1; 4, 3], sum: 1
-debug- range: [0, 2; 3, 4], sum: -14
-debug- range: [1, 2; 4, 4], sum: -9
-debug- Checking matrices: 3x3
-debug- range: [0, 0; 3, 3], sum: -11
-debug- range: [1, 0; 4, 3], sum: 5
-debug- range: [0, 1; 3, 4], sum: -13
-debug- range: [1, 1; 4, 4], sum: 2
-debug- Checking matrices: 3x4
-debug- range: [0, 0; 3, 4], sum: -8
-debug- range: [1, 0; 4, 4], sum: 6
-debug- Checking matrices: 4x1
-debug- range: [0, 0; 4, 1], sum: 4
-debug- range: [0, 1; 4, 2], sum: 9
-debug- range: [0, 2; 4, 3], sum: -17
-debug- range: [0, 3; 4, 4], sum: 1
-debug- Checking matrices: 4x2
-debug- range: [0, 0; 4, 2], sum: 13
-debug- range: [0, 1; 4, 3], sum: -8
-debug- range: [0, 2; 4, 4], sum: -16
-debug- Checking matrices: 4x3
-debug- range: [0, 0; 4, 3], sum: -4
-debug- range: [0, 1; 4, 4], sum: -7
-debug- Checking matrices: 4x4
-debug- range: [0, 0; 4, 4], sum: -3
SumOpCount: 100
Range: [1, 0; 4, 2], sum: 15
Matrix: 3 2
9 2
-4 1
-1 8
On 12 окт, 20:54, "Lego Haryanto" <[EMAIL PROTECTED]> wrote:
> The explanation above is correct ... O(n^3) is enough.
>
> If you're able to solve the one dimensional array in O(n), then you can
> solve the 2D case in O(n^3).
>
> For each row-range [a..b], we'll compute the maximum contiguous subarray
> with the O(n) above. To achieve O(n^3), this means that for each column c,
> we need to have the sum of arr[a][c], arr[a+1][c], ... arr[b-1][c] handy (
> i.e. in O(1) algo). But that's fine, we can precalc them using prefix-sum
> (O(n^2)).
>
> Look at my post inwww.algorithmist.com... search for UVa problem 108 -
> Maximum Sum.
>
> Good luck.
>
> On 10/12/07, Andrey <[EMAIL PROTECTED]> wrote:
>
>
>
> > Does anyone knew more effective solution then DP?
>
> > On Oct 12, 3:46 pm, Andrey <[EMAIL PROTECTED]> wrote:
> > > I doubt It will be O(n^3)..
> > > Dynamic programming algorithm, by size of submatrix, will give at
> > > least O(N ^ 4), won't it?
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
