Maximum Sum Submatrix
Method 1 :
This is in O(n^4) using dynamic programming. A huge improvement over the naive o(n^6), where the complexity to calculate the sum of a sub matrix was O(n^2). This time has been reduced to O(1) using DP.
#include <iostream> #include <climits> #define N 3 using namespace std; int sumMatrix[N][N]; void preComputeMatrix(int a[][N]) { for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(i==0 && j==0) sumMatrix[i][j] = a[i][j]; else if(i==0) sumMatrix[i][j]+=sumMatrix[i][j-1] + a[i][j]; else if(j==0) sumMatrix[i][j]+=sumMatrix[i-1][j] + a[i][j]; else sumMatrix[i][j]+=sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1] + a[i][j]; } } } int computeSum(int a[][N],int i1,int i2,int j1,int j2) { if(i1==0 && j1==0) return sumMatrix[i2][j2]; else if(i1==0) return sumMatrix[i2][j2] - sumMatrix[i2][j1-1]; else if(j1==0) return sumMatrix[i2][j2] - sumMatrix[i1-1][j2]; else return sumMatrix[i2][j2] - sumMatrix[i2][j1-1]- sumMatrix[i1-1][j2] + sumMatrix[i1-1][j1-1]; } int getMaxMatrix(int a[][N]) { int maxSum = INT_MIN; for(int row1=0; row1<N; row1++) { for(int row2=row1; row2<N; row2++) { for(int col1=0; col1<N; col1++) { for(int col2=col1; col2<N; col2++) { maxSum = max(maxSum,computeSum(a,row1,row2,col1,col2)); } } } } return maxSum; } int main( void ) { int a[N][N] = {{-1,-2,-3},{-10,-5,-15},{6,-8,-20}}; preComputeMatrix(a); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) cout<<sumMatrix[i][j]<<" "; cout<<endl; } cout<<getMaxMatrix(a); return 0; }
Method 2
Kadane’s Algorithm 2D. Overall complexity is O(n^3)
Check out http://www.algorithmist.com/index.php/UVa_108 for the algorithm
#include <iostream> #include <climits> using namespace std; int a[101][101]; int kadane2D(int n) { int *columnSum = new int[n]; int s=INT_MIN,S=INT_MIN,t; for(int row = 0; row<n; row++) { for(int i=0; i<n; i++) columnSum[i] = 0; for(int x = row; x<n; x++) { s = INT_MIN; t = 0; for(int i=0; i<n; i++) { columnSum[i]+=a[x][i]; t+=columnSum[i]; if(t>s) s = t; if(t<0) t = 0; } if(s>S) S = s; } } delete [] columnSum; return S; } int main( void ) { int n; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>a[i][j]; } } cout<<kadane2D(n)<<endl; return 0; }
March 16, 2012 Posted by ronzii | C++, Dynamic Programming | 2d, algorithms, amazon, C++, Dynamic Programming, kadane, maximum, subarray | Leave a comment
April 2024 S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Categories
- Brain Teaser (1)
- C++ (101)
- Data Structures (10)
- Dynamic Programming (16)
- Fun (2)
- Sorting (6)
Archives
Top Clicks
- None
Top Posts
-
Join 39 other subscribers
Search
Project Euler Statistics
Blog Stats
- 89,108 hits
Tags
Algorithms algorithms amazon array backtracking balanced binary search Brain Teaser BST C++ common Data Structures Diameter Dijkstra Doubly dp Dynamic Programming euler fibonacci Fun google graph hash heap Intern interview Iterative Java jumps kadane KMP knapsack linked list longest lrs matrix median memoization miller rabin minimum mirror modular exponentiation Morris optimal optimized palindrome Placement precomputation prime probability Programming Project Euler rabin karp random recursion repeat rolling hash rotation SAP segment tree sieve Sliding sorting SPOJ STL String substring Suffix summation swap traversal tree Trie unlucky numbers Window