Hope this helps :
space: o(n^2)
time: o(n^2)
#include<iostream>
using namespace std;
inline int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
char str[7]="hello";
int arr[3][3]={
{15,2,3},
{4,5,6},
{7,8,9},
};
int sum[3][3]={0};
int n=3,i,j;
sum[0][0]=arr[0][0];
for(i=1;i<n;i++)
{
sum[0][i]=sum[0][i-1]+arr[0][i];
sum[i][0]=sum[i-1][0]+arr[i][0];
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
}
}
int min=INT_MAX;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
int
k=max(max(sum[i][j],sum[n-1][n-1]+sum[i][j]-sum[n-1][j]-sum[i][n-1]),max(sum[i][n-1]-sum[i][j],sum[n-1][j]-sum[i][j]));
if(min>k)
min=k;
}
}
cout<<"ans : "<<min;
}
On Fri, Aug 17, 2012 at 6:36 PM, sahil taneja <[email protected]>wrote:
>
> @Hraday
> worst case complexity of your algorithm comes out to be O(n^4)..
> What I was thinking is precompute sums of all the rectangles in a sum
> matrix ..using dynamic programming because I read some where that sum of
> rectangles in a matrix has an optimal substructure property..
>
> So we can get sum of all the partitioned rectangles in O(1) reducing our
> complexity to O(n^2)..So, our job now is just to precompute the matrix..
>
>
> On Sunday, 12 August 2012 17:48:07 UTC+5:30, sahil taneja wrote:
>
>> Divide 2D array into 4 parts. Compute sum of each partition and get max
>> value from the four of them. For all possible partitions get min value of
>> such max values computed.
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/dOI2SIuw-nMJ.
>
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Abhinav Sikri
B.E. (Computer Engineering)
Netaji Subhas Institute of Technology
Dwarka, New Delhi
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
