Lets get started again!!!

Go down

Lets get started again!!!

Post  shivang on Wed Aug 27, 2008 7:13 am

Given a 2-dimensional array of positive and negative integers,
find the sub-rectangle with the largest sum.
The sum of a rectangle is the sum of all the elements in that rectangle.
In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
A sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array.

As an example, the maximal sub-rectangle of the array:

matrix2

0......2.....-7....0
9......2......-6....2
-4.....1......-4....1
-1.....8...... 0.....-2


is in the lower-left-hand corner:

matrix2

9......2
-4.....1
-1.....8

and has the sum of 15.
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: Lets get started again!!!

Post  ankurgutpa on Thu Oct 23, 2008 6:31 pm

finally it's done..
first of all the answer of your example is
0.......2
9......2
-4.....1
-1.....8
ie left half matrix of sum 17.
Consider given matrix A (mxn)
Optimal Structure
any col j to col k of row i of matrix A can be in maximum sum submatrix. for row i calculate sum from col j to col k(say s1) . Now come to next row (i+1) and calculate sum from col j to col k(say s2), If this sum(s2) + sum of col j to col k of previous row(s1) is greater s2 then for this row (i+1) and col j to col k, s1+s2 should be an optimal solution else s2 will be an optimal solution.
Recursive Solution

Max submatrix
i <=m and j<=k<=n
sum[.i][j][k]=A[j][k] if j=k
.....................= sum[.i][j][k]+A[.i][k]

this table will get sum of row i from col j to col k. Since j<=k it will use only upper triangular matrix for each i. This table will help in DP solution

dp[.i][j][k]=sum[.i][j][k] if i=1
...................=max(sum[.i][j][k] , sum[.i][j][k]+dp[i-1][j][k] )
It means maximum sum if col j to col k of A is taken ,till row i.

Computing Optimal Cost
i=1 to m
...j=1 to n
....sum[.i][j][j]=A[.i][j]
........k=j+1 to n
..........sum[.i][j][k]=sum[.i][j][k-1]+A[.i][k]
j=1 to n
...k=j to n
.....dp[1][j][k]=sum[1][j][k]
i=1 to m
...j=1 to n
....k=j to n
.......dp[.i][j][k]=max(sum[.i][j][k],sum[.i][j][k]+sum[.i][j][k])
return dp

Constructing Optimal Solution
from-row, to-row, from-col, to-col , max-sum=0
i=1 to m
...j=1 to n
......k=j to n
........if dp[.i][j][k] > max
...........max=dp[.i][j][k]
...........to-row=i , from-col=j , to-col=k
from-row=to-row
while dp[to-row][from-col[to-col] != sum[to-row][from-col][to-col]
.....from-row-=1
print A from [from-row....to-row][from-col....to-col] and sum cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum