Problem of Find the maximum 2d subarray 17.23 in v1.4.7

#1

Hi,

In the description, there is a sentence saying “Suppose we know the length s of the largest square region that has A[i+1][j+1] as its bottom-left corner. Then the length of the side of the largest square with A[i,j] as its bottom-left corner is at most s+1, …”

I have two problems of it, first one minor, second one is major.

(1) A[i,j] means A[i][j] right? So it would better if keep the writing style unchanged, just write it as A[i][j] all the time would better?

(2)
I doubt the correctness of the argument. Please see the example below

suppose i==3, j==0, clearly the square with left-bottom corner (i+1,j+1) has side length s==2, and square with left-bottom corner (i,j) has side length s’==4

s’ == s+2.

This example contradicts to the argument that it is at most s+1.

1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 1 1 0 0

Is there a problem with my understanding or the description is problematic?

Thanks

0 Likes
#2

Hey Pete,

Sorry for my late reply. Again, thanks for your question which gives me another chance to review those materials we wrote before. Following is my reply to your questions:

(1) We somehow misused the notation of 2D subarray but in the notation section, you should notice that we actually define both of those two usages are the notation for 2D subarray. However, I agree that we should unify the notation usage for sure.

(2) For the example you mentioned, s should be 3 and s’ is equal to 4. I don’t see any problem in the example you mentioned.

Please let me know if you have any problem.

Tsung-Hsien

0 Likes
#3

Hi Tsung Hsien,

Thanks for the reply. For (2) s should be 2. Why? Because we are talking about the square with (4,1) as the bottom-left corner. Then the length of of edge of square with (3,0) as left bottom corner is 4.

I am referring to the sentence in the book “Suppose we know the length s of the largest square region that has A[i+1][j+1] as its bottom-left corner. Then the length of the side of the largest square with A[i,j] as its bottom-left corner is at most s+1, …”

let me know whether you got my point.

0 Likes
#4

Hey Pete,

There is a coordinate system problem here. If we treat the top-left corner as (0, 0), which is what you used, then the s value of (4, 1) is 1 because it already reaches the boundary. As a result, the s value of (3, 0) is at most 2 in fact. The reason you have this confusion is because we use bottom-left as (0, 0), and you use top-left corner as (0, 0). Moreover, the s value of (0, 0) in your example is 4 because the s value of (1, 1) is 3.

Please let me know if you have any problem.

0 Likes
#5

ok that makes sense. thanks.

0 Likes