Can we MAP this variant to Finding the largest Bound rect in a BAR
graph..?
Think so.
I can be done by Iterative Usage of the Same algo(as Bar grph) at evry
row from Bottom.
Open for Suggestions ...
On Mar 12, 11:40 pm, "Karthik Singaram L" <[EMAIL PROTECTED]>
wrote:
> Another variant...(or rat
Another variant...(or rather wanted to say in my previous post)
How do you find a maximum square of all ones in a binary matrix of 0s and
1s?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
Yes, I agree that the logic that I gave only works for maximum squares from
[1][1].
On an interesting extension to the problem, special case that to squares of
maximum sum.
How to find the Square of Max sum in a 2D matrix consisting of both
+ve and -ve numbers,,,
--~--~-~--~~--
On 3/12/07, Balachander <[EMAIL PROTECTED]> wrote:
>
> How to find the Rectangle of Max sum in a 2D matrix consisting of both
> +ve and -ve numbers,,,
>
Is any one aware of any theoretical lower bounds on this problem?
I remember reading about this in ``Programming Pearls'' by Jon
Bentley, where
First, find a prefix-sum on each column (O(N^2)). This is done so that we
can later on compute the sum of consecutive rows in O(1) complexity.
Now, observe all possible row-pairs (O(N^2)), and for each pair, you can see
that we can get the sum of each "column" in O(1) complexity. This will
provi
On 3/12/07, Balachander <[EMAIL PROTECTED]> wrote:
>
> How to find the Rectangle of Max sum in a 2D matrix consisting of both
> +ve and -ve numbers,,,
>
This solution is based on a similar variant of the problem,
calculating maximum contiguous sub-array in one dimension. That
problem can be solve
The above code computes sum[i][j] =maximum sum for a subarray which always
starts at 1,1 and ends at i,j which is not quite right!
On 3/12/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
> use the following logic to create a table of sums (assume that the given
> array is a):
>
> sum[i][j] =
use the following logic to create a table of sums (assume that the given
array is a):
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
sum[i][j] = 0 for the boundary cases like i = -1 or j= -1
Then you can traverse the sum array to find the maximum sum.
Overall O(n^{2})
--~--~---
