CareerCup

package problems;

import Definition.Matrix;

public class MaximumSumMatrix {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[][] aMatrix = { { 2, 40, -8 }, { -12, 35, -8 }, { 12, -9, -8 } };
		// Matrix.initialize(aMatrix);
		Matrix.printMatrix(aMatrix);
		findMaximumSubMatrix(aMatrix);
	}

	private static void findMaximumSubMatrix(int[][] aMatrix) {
		// TODO Auto-generated method stub

		int[] oneD;
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < aMatrix.length; i++) {
			oneD = new int[aMatrix[0].length];
			int current = 0;
			int maxCurrent = Integer.MIN_VALUE;
			for (int k = i; k < aMatrix.length; k++) {
				current = 0;
				for (int j = 0; j < aMatrix[0].length; j++) {
					oneD[j] = oneD[j] + aMatrix[k][j];
					current = current + oneD[j];
					if (current > maxCurrent) {
						maxCurrent = current;
					}
					if (current < 0) {
						current = 0;
					}
				}
				if (maxSum < maxCurrent)
					maxSum = maxCurrent;
			}
		}
		System.out.print(maxSum);
	}
}

see there:
http://www.mathlinks.ro/viewtopic.php?p=385650#385650

There is a O(N^3) algorithm.

//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;
    }
}

Its a dymanic programming problem; Can anyone write an recurrence equation for this problem.

I cant think of a way to use subproblem to form an equation.

Can anyone post any soluton to this ?

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.

Typo in FindSubsequenceWithMaxSum() above:

if (sum <= 0 || (sum + Array[i]) < 0)

...should read:

if (sum <= 0 || (sum + Array[i]) <= 0)

can you post the exact question

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.

Sample example:
2 10 8 3
-8 14 -1 4
-6 -1 8 -2
1 8 7 3
8 2 -10 -8

Then answer should be:
10 8 3
14 -1 4
-1 8 -2
8 7 3

see there:
http://www.mathlinks.ro/viewtopic.php?p=385650#385650

There is a O(N^3) algorithm.

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.

http://alien.dowling.edu/~rohit/mindsports/viewtopic.php?t=139

Kadanes 2D algorithm

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();
    } 
}

Dynamic table fill-up:
/* As solution[i-1][j-1] will be counted twice in solution matrix fill-up we need to subtract it */

solution[i][j] = matrix[i][j] + (solution[i-1][j] + solution[i][j-1] - solution[i-1][j-1])