sub-rectangle with the largest sum on N*N array

[eman 22]

I want easy algorithm with minimum order to get the sub-rectangle with the largest sum in an array
for example
array as a input
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

sub-rectangle
9 2
-4 1
-1 8

maximum sum of its sub-rectangle is : 30

Please I want the idea of this problem beacuse I think too much but I didn't reach to nothing

After thinking long, I found that this sub-rectangle may be include the largest positive number in array but what's the solution if in this sub-rectangle may include negative numbers the maximum of it may largest than the Positive numbers in this sub-rectangle .
sorry for the long thread
thanks,

[AuburnMathTutor]

Interesting.

You could always try *every* rectangle and take the maximum sum. You would have to pick your top, left, right, and bottom coordinate independently in this approach. Since you would have sqrt(n) choices for each (well, not really, but on the order of that many) where n is the total size of the array, I suppose you're talking about O(n^2)... plus a little to actually sum the elements, and I guess this might make it as high as O(n^3). You could be tricky in how you compute the sums, though, and by saving subrectangle sums I bet you could easily make the brute-force version O(n^2). Since this would be fairly easy to do, there's no excuse for doing worse than this. You will have to look at every element of the array, so you will be at least O(n).

So whatever your answer is, it will be somewhere between O(n^2) and O(n). Not a huge range of difference.

Are there any properties we can exploit? If you have a rectangle, could a subrectangle be better? Yes, sure. If you have a rectangle, could a superrectangle be better? Again, yes. Not a lot of help there.

I don't know, man. I hope this post has been of some meager help, though. I'll think about it some more and let you know if I come up with anything.

[Aranarth]

You'll have to test every possible subrectangle, however you can start at the top-left and keep going left, so you can subtract the most left column of the subrectangle and add the new column each step. When you're done with the row, start with the next one.

[AuburnMathTutor]

^ Are you sure you'll have to check *every* rectangle? That's not obvious to me, especially given the fact that you can do better than that on the maximum subsequence sum problem, to which this seems related.

[eman 22]

I meant sub-rectangle not subsquence
for example
array of size 2*2
4 3
2 -9
subsquence is
4 3
2
sum is 9
sub-rectangle is
4 3
sum is seven
in this array we have 9 sub-rectangle
each number consider a sub-rectangle
5.(the fifth sub-rectangle
the whole array
6.(sixth sub-rectangle)
4
2
7.
3
-9
8.
4 3
9.
2 -9

[AuburnMathTutor]

I know, but it's not clear to me that the best you can do is to check every subrectangle, since it's just as easy to say that you must check every subsequence in the maximum subsequence sum problem. It's not true in that instance, and it might not be true here either.

Plus, I am no longer going to entertain the thought of helping you, since you have cross-posted and didn't even take my advice to post in the appropriate forum. For shame.

[Aranarth]

Are you sure you'll have to check *every* rectangle? That's not obvious to me, especially given the fact that you can do better than that on the maximum subsequence sum problem, to which this seems related.

No, you can't do better on the maximum subsequence sum problem, because you have to look at every value.
I don't think you read my post properly.

[AuburnMathTutor]

^ Perhaps I am reading it wrong. There's a difference between checking every value (which I agree you'll have to do) and checking every subsequence (which you indeed do not have to do) in the MSS problem.

I agree that you will have to check every value in the maximum subrectangle sum problem, but I am hesitant to agree that you will have to check every subrectangle, for the same reason. It's possible you're right when you say you'll have to check every subrectangle, but you might be able to get away with less than O(n^2). I don't know. I apologize if I'm reading your post incorrectly.

[Aranarth]

For the MSS problem you build the sum of the most left subsequence then keep advancing through the main sequence by subtracting the most left element of the subsequence from the sum and adding the next element right after the subsequence.
So that's similar to the method I suggested for the rectangle.
If you can think of a more efficient method, go ahead. There's nothing that can be in a better class than O(n²), though (assuming n is the side length of the source square).

[mrnutty]

@OP: First work to get a O(n) solution to the maximum sum problem for a 1d array.
And after you get that, use that to your advantage for this problem. At best, you will
do O(n^3), if I'm not mistaken.

[AuburnMathTutor]

For the MSS problem you build the sum of the most left subsequence then keep advancing through the main sequence by subtracting the most left element of the subsequence from the sum and adding the next element right after the subsequence.

Agreed...

So that's similar to the method I suggested for the rectangle.

Possibly it is. I focused mostly on your assertion that you had to check every subrectangle, which may simply be a poorly-worded description of what you really had in mind. On the other hand, the literal meaning of that assertion may indeed be true; I just hesitate to declare that as truth when a similar problem has a better solution.

If you can think of a more efficient method, go ahead. There's nothing that can be in a better class than O(n²), though (assuming n is the side length of the source square).

First off, what is the efficiency of your method? I describe the potential efficiencies of my brute-force method with and without some rudimentary memoization. Probably better to let you do your own, lest I continue to have difficulties in the interpretation. I do agree that that you'll never do any better than O(n), where n is the number of elements, or O(n^2) where n is the length of the side of the input array (where the array happens to be square). That's pretty easy to see, and it's also true of the MSS problem... you have to look at all the elements before you can answer the question.

[AuburnMathTutor]

-