Agilent Technologies Microsoft Interview Question
Software Engineer / Developers//Idea taken from stackoverflow
int findMaximumSubMatrix(int** matrix, int *top, int *left, int *bottom, int *right, unsigned int dim){
int i, j, k, maxSum, localMax, ret =0;
int **ps=NULL;
int *pos=NULL, *sum = NULL;
*top = -1;
*left = -1;
*bottom = -1;
*right = -1;
if (matrix == NULL || dim <= 0)
return -1;
//computing the vertical prefix sum for columns
ps = malloc (sizeof(int *) * dim);
if (ps == NULL)
return -1;
for (i = 0; i<dim;i++)
{
ps[i]=malloc (sizeof(int)*dim);
if (ps[i] == NULL) {
ret = -1;
goto fail;
}
}
for (i = 0; i < dim; i++) {
for (j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}
maxSum = matrix[0][0];
*top = 0; *left = 0; *bottom = 0; *right = 0;
sum = malloc(sizeof(int)*dim);
if (sum == NULL){
ret =-1;
goto fail;
}
pos = malloc(sizeof(int)*dim);
if (pos == NULL){
ret =-1;
goto fail;
}
for (int i = 0; i < dim; i++) {
for (int k = i; k < dim; k++) {
// Kandane over all columns with the i..k rows
memset(sum, 0, dim*sizeof(int));
memset(pos,0, dim*sizeof(int));
localMax = 0;
//we keep track of the position of the max value over each Kandane's execution
// notice that we do not keep track of the max value, but only its position
sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
for (int j = 1; j < dim; j++) {
if (sum[j-1] > 0){
sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = pos[j-1];
}else{
sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = j;
}
if (sum[j] > sum[localMax]){
localMax = j;
}
}//Kandane ends here
if (sum[localMax] > maxSum){
/* sum[localMax] is the new max value
the corresponding submatrix goes from rows i..k.
and from columns pos[localMax]..localMax
*/
maxSum = sum[localMax];
*top = i;
*left = pos[localMax];
*bottom = k;
*right = localMax;
}
}
}
for(i = *top; i <= *bottom; i++){
for(int j = *left; j <= *right ; j++){
printf("%d ", matrix[i][j]);
}
printf("\n");
}
fail:
for (j=0;j<dim;j++) {
if (ps[i])
free(ps[i]);
}
if (ps)
free(ps);
if(pos)
free(pos);
if(sum)
free(sum);
return ret;
}
private void reset(int[] a) {
for (int index = 0; index < a.length; index++) {
a[index] = 0;
}
}
//Modified earlier post ...
//Idea taken from stackoverflow
int findMaximumSubMatrix(int** matrix, int *top, int *left, int *bottom, int *right, unsigned int dim){
int i, j, k, maxSum, localMax, ret =0;
int **ps=NULL;
int *pos=NULL, *sum = NULL;
*top = -1;
*left = -1;
*bottom = -1;
*right = -1;
if (matrix == NULL || dim <= 0)
return -1;
//computing the vertical prefix sum for columns
ps = malloc (sizeof(int *) * dim);
if (ps == NULL)
return -1;
for (i = 0; i<dim;i++)
{
ps[i]=malloc (sizeof(int)*dim);
if (ps[i] == NULL) {
ret = -1;
goto fail;
}
}
for (i = 0; i < dim; i++) {
for (j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}
maxSum = matrix[0][0];
*top = 0; *left = 0; *bottom = 0; *right = 0;
sum = malloc(sizeof(int)*dim);
if (sum == NULL){
ret =-1;
goto fail;
}
pos = malloc(sizeof(int)*dim);
if (pos == NULL){
ret =-1;
goto fail;
}
for (int i = 0; i < dim; i++) {
for (int k = i; k < dim; k++) {
// Kandane over all columns with the i..k rows
memset(sum, 0, dim*sizeof(int));
memset(pos,0, dim*sizeof(int));
localMax = 0;
//we keep track of the position of the max value over each Kandane's execution
// notice that we do not keep track of the max value, but only its position
sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
for (int j = 1; j < dim; j++) {
if (sum[j-1] > 0){
sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = pos[j-1];
}else{
sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = j;
}
if (sum[j] > sum[localMax]){
localMax = j;
}
}//Kandane ends here
if (sum[localMax] > maxSum){
/* sum[localMax] is the new max value
the corresponding submatrix goes from rows i..k.
and from columns pos[localMax]..localMax
*/
maxSum = sum[localMax];
*top = i;
*left = pos[localMax];
*bottom = k;
*right = localMax;
}
}
}
for(i = *top; i <= *bottom; i++){
for(int j = *left; j <= *right ; j++){
printf("%d ", matrix[i][j]);
}
printf("\n");
}
fail:
for (j=0;j<dim;j++) {
if (ps[i])
free(ps[i]);
}
if (ps)
free(ps);
if(pos)
free(pos);
if(sum)
free(sum);
return ret;
}
Its a dymanic programming problem; Can anyone write an recurrence equation for this problem.
See the answer in this page: http://alien.dowling.edu/~rohit/wiki/index.php?title=Google_Interview_Questions#Suppose_you_have_an_NxN_matrix_of_positive_and_negative_integers._Write_some_code_that_finds_the_sub-matrix_with_the_maximum_sum_of_its_elements.
Let me know what you guys think of this solution:
I'm assuming that a submatrix has to be rectangular, e.g. you create the submatrix by removing some combination of rows and columns from the perimeter of the matrix. So your algorithm would be something like this:
Add up the totals of all the rows and columns on the perimeter of the matrix. If any of them add up to a number less than zero, remove those, and this will be your submatrix with a maximum sum. Keep doing this until none of the rows or columns have a negative sum. (Note: I'm assuming that the matrix counts as a submatrix of itself. If not, just remove the row or column with the smallest sum in the first step.)
i started with a o(n^6) solution and was easily able to come to a o(n^4) one, but it took lot of time to narrow it down to o(n^3) . I have heard there is a o(n^2.69) solution as well.
its's very easy
solve recursively
base case : n=1
iterative case :
to find for m*n, find for m-1 * n-1 ,call it a
b = a + sum of upper row - mat[0][0]
c = a + sum of first col - mat[0][0]
d = a + sum of upper row + first col - mat[0][0]
return max(a,b,c,d);
sexy....
then
Given an O(N) method of finding the offset & length of the subsequence of elements with the highest sum in a one-dimensional array of N positive & negative integers:
FindSubsequenceWithMaxSum (int *Array, uint N)
{
unsigned long sum = 0, maxSum = LONG_MIN;
unisgned int offset, length,
maxOffset = 0, maxLength = 1;
for (uint i = 0; i < N; i++)
{
if (sum <= 0 || (sum + Array[i]) < 0)
{
sum = (long) Array[i];
offset = i;
length = 1;
}
else
{
sum += (long) Array[i];
length++;
}
if (sum > maxSum)
{
maxSum = sum;
maxOffset = offset;
maxLength = length;
}
}
/* Done: maxSum, maxOffset, maxLength */
}
...an O(N^2.69) solution is as follows:
FindSubmatrixWithMaxSum (int *Matrix, uint N)
{
unsigned long maxSum = LONG_MIN;
unsigned int maxRow = 0, maxColumn = 0,
maxWidth = 1, maxHeight = 1;
/* Find max subseq (height=?, width=1) across all columns */
for (uint col = 0; col < N; col++) { ... }
/* Find max subseq (height=1, width=?) across */
/* all uncompressed rows */
for (uint row = 0; row < N; row++) { ... }
/* Do row compression & compute max row subseqs */
for (uint augendRow = 0; augendRow < (N-1); augendRow++)
{
for (uint addendRow = (augendRow+1);
addendRow < N;
addendRow++)
{
uint maxSumAfterCompression = INT_MIN,
maxColumnAfterCompression = 0,
maxLengthAfterCompression = 1;
for (uint col = 0; col < N; col++)
{
/* Compress this column, e.g. : */
/* Matrix[augendRow][col] += */
/* Matrix[addendRow][col]; */
/* ...then track max subseq of row so far */
}
if (maxSumAfterCompression > maxSum)
{
maxSum = maxSumAfterCompression;
maxRow = augendRow;
maxColumn = maxColumnAfterCompression;
maxWidth = maxLengthAfterCompression;
maxHeight = 1 + addendRow - augendRow;
}
}
}
/* Done: maxSum, maxRow, maxColumn, maxWidth, maxHeight */
}
For example, given an N=4 matrix:
row 0 : a0 a1 a2 a3
b0 b1 b2 b3
c0 c1 c2 c3
d0 d1 d2 d3
...the first for(augendRow) loop iteration will compute max subsequences for the following row combinations:
(a0+b0 a1+b1 a2+b2)
(a0+b0+c0 a1+b1+c1 a2+b2+c2)
(a0+b0+c0+d0 a1+b1+c1+d1 a2+b2+c2+d2)
In all, max subsequences are generated (at O(N)) for a total of (N^2)/2 combinations, thus O((N^3)/2) or O(N^2.69).
Practical platform-specific optimizations may include:
- Transposing matrix (e.g. in h=?/w=1 loop) to improve locality of reference in innermost nested loop
- Performing multiple row compressions (augend-only or following rows) in the innermost loop
Note that the use of "long" types for "sum" variables may not suffice for underflow/overflow mitigation for large N.
It is like finding maximum sum in sub array... but instead of single dimension it is a matrix now...
In a m x n matrix, find a submatrix p x q such that sum of all the elements in it is maximum as compared to any other submatrix of any size. Ofcourse the matriz contains negative elements otherwise the question doesn't make sense.
O(n^3) where n is the number of cells in the matrix.
==============
for each cell i
..use i as the top left corner of all candidate rectangles/
..calculate the sum of all possible candidate rectangles (n^2)
..only record the max sum for i.
In the end, we have the max sum for each cell, then find the max sum for all cells.
Note:
Negative and Positive numbers are also present.
Solution 1:
List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.
Solution 2:
We construct an output array from the input array in the following manner:
inputArr[m][n] be the input array.
And let us make another array outputArr[m][n] with all fields set to zero by default.
Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].
So determine outputArr[i][j] =
inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]
Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]
Now we can run an algorithm similar to the first solution only difference is that finding the sum is easier now.
For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.
You can find the solution here at dailyjobquestions.com/2011/10/10/max-submatrix/
Here's the dynamic programming implementation in C++
typedef struct info{int i; int j; int max;} info;
int row(int** a, int i, int j1, int j2) {
int s = 0;
for (int j = j1; j <= j2; j++) s += a[i][j];
return s;
}
int column(int** a, int j, int i1, int i2) {
int s = 0;
for (int i = i1; i <= i2; i++) s += a[i][j];
return s;
}
void max_matrix(int** a, int n) {
info** p = new info*[n];
for (int i = 0; i < n; i++) p[i] = new info[n];
info max_info = {0, 0, a[0][0]};
int max_i = 0;
int max_j = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = (info){i, j, a[i][j]};
if (i > 0) {
info up = p[i-1][j];
up = (info){up.i, up.j, up.max + row(a, i, up.j, j)};
if (up.max > p[i][j].max) p[i][j] = up;
}
if (j > 0) {
info left = p[i][j - 1];
left = (info){left.i, left.j, left.max + column(a, j, left.i, i)};
if (left.max > p[i][j].max) p[i][j] = left;
}
if (max_info.max < p[i][j].max) {
max_info = p[i][j];
max_i = i;
max_j = j;
}
}
}
printf("The submatrix starts at (%i, %i) and ends at (%i, %i) and the sum is %i", max_info.i, max_info.j, max_i, max_j, max_info.max);
for (int i = 0; i < n; i++) delete[] p[i];
delete[] p;
}
The easiest solution is in deep first search:
each time splitting matrix by vertical or horizontal line on two:
if one submatix sum is negative and another submatrix sum
is positive, then those with positive sum is better than the original
matrix, use it for next step.
The idea is described in the code below (for the case of vector):
from random import randint;
maxSum = [0];
bestMatrix = [0];
def DFS(a):
print a;
if sum(a) > maxSum[0]:
maxSum[0] = sum(a);
bestMatrix[0] = a;
for splitter in range(1, len(a)):
leftSum = sum(a[:splitter]);
rightSum = sum(a[splitter:]);
if leftSum > 0 and rightSum < 0:
DFS(a[:splitter]);
elif leftSum < 0 and rightSum > 0:
DFS(a[splitter:])
a = [randint(0, 20) - 10 for item in range(10)];
print a;
DFS(a);
print maxSum[0];
print bestMatrix[0];
I came with this solution in java, the first comments says it has a solution but is incorrect
import java.util.*;
public class HelloWorld {
public static void main(String []args){
int[][] aMatrix = {
{ 2, 40, -8 }, { -12, 35, -8 }, { 12, -9, -8 }
};
Object[] subMatrix = longestSubmatrixSum(aMatrix);
System.out.println(Arrays.toString(subMatrix));
}
public static Object[] longestSubmatrixSum(int [][] matrix) {
int cols = matrix[0].length,
rows = matrix.length,
totalMatrixElements = cols * rows,
arrayIndex = 0,
maxSum = -9999999;
int [] plainArray = new int[totalMatrixElements];
List trackNumbers = new ArrayList(),
auxTrackNumbers = new ArrayList();
for (int i = 0; i < rows; i++) {
for (int k = 0; k < cols; k++) {
plainArray[arrayIndex] = matrix[i][k];
arrayIndex++;
}
}
for (int i = 0; i < totalMatrixElements; i++) {
int currentSum = 0;
for (int k = i; k < totalMatrixElements; k++) {
currentSum = plainArray[k] + currentSum;
auxTrackNumbers.add(plainArray[k] + "");
if (maxSum < currentSum) {
maxSum = currentSum;
trackNumbers = ((List) ((ArrayList) auxTrackNumbers).clone());
}
}
// We clear values so we now is a new line
auxTrackNumbers.clear();
}
System.out.println("max sum is:" + maxSum);
return trackNumbers.toArray();
}
}
- MaYank July 15, 2010