# Lets get started again!!!

## Lets get started again!!!

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.

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.

**shivang**- Posts : 22

Join date : 2008-08-11

Age : 30

Location : Tondon 174

## Re: Lets get started again!!!

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)

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.

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.

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

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

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

**ankurgutpa**- Posts : 44

Join date : 2008-08-10

Age : 31

Location : Tandon 72

Page

**1**of**1****Permissions in this forum:**

**cannot**reply to topics in this forum