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 <sahiltanej...@gmail.com>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 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. > -- 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 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.