Let f[r, c] denote the sum of rectangular subarray ofM with one corner at entry [1, 1] and the other at [r, c]. This can be computed in O(n2) time. Observe that the sum of any rectangular subarray of M can be computed in constant time given the table f. This yields an O(n4) algorithm; simply guess the lower-left and the upper-right corner of the rectangular subarray and use the f table to compute its sum. Here is how we can get O(n3) time. Recall that the maximum sum substring of a 1 dimensional array algorithm simply walks through the array one entry at a time and keeps a running total of the entries. If this total ever becomes negative then set it to 0. Output the largest of these totals. Use this as an auxiliary function to solve the two dimensional problem in the following way. Guess the top and bottom row r1 and r2 of the subarray. Using the table f computed previously and the maximum sum substring algorithm for 1 dimensional arrays we can determine the maximum sum rectangular subarray with top row r1 and bottom row r2 in linear time.
On Fri, Feb 18, 2011 at 7:11 PM, DIPANKAR DUTTA <dutta.dipanka...@gmail.com>wrote: > http://dsalgo.blogspot.com/2008/05/max-sum-sub-matrix.html > > > On Fri, Feb 18, 2011 at 7:10 PM, DIPANKAR DUTTA < > dutta.dipanka...@gmail.com> wrote: > >> http://dsalgo.blogspot.com/2006/07/maximum-sub-array-sum.html >> >> >> On Fri, Feb 18, 2011 at 2:51 AM, bittu <shashank7andr...@gmail.com>wrote: >> >>> you have 2-d array, with m length and n width.You are also given k, >>> ( k<=n && k<=m ). >>> Now, select a square of size k, which returns maximum sum.In Minimum >>> Time Complexity >>> >>> >>> Thanks & Regards >>> Shashank. >>> >>> >>> >>> >>> -- >>> 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 >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> DIPANKAR DUTTA >> M-TECH,Computer Science & Engg. >> E&C Dept,IIT ROORKEE >> Uttarakhand , India – 247667 >> ------------------------------------------- >> website:http://people.iitr.ernet.in/shp/09535009/Website/index.html >> ph no-09045809987 >> Lab: 286454 >> email:dipan...@iitr.ernet.in >> >> > > > -- > DIPANKAR DUTTA > M-TECH,Computer Science & Engg. > E&C Dept,IIT ROORKEE > Uttarakhand , India – 247667 > ------------------------------------------- > website:http://people.iitr.ernet.in/shp/09535009/Website/index.html > ph no-09045809987 > Lab: 286454 > email:dipan...@iitr.ernet.in > > -- DIPANKAR DUTTA M-TECH,Computer Science & Engg. E&C Dept,IIT ROORKEE Uttarakhand , India – 247667 ------------------------------------------- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
