Given a 2D array, find the maximum sum subarray in it

The usual approach is for every rectangle in the matrix, find the sum and compare it with maximum sum. This takes O(n4) time complexity coz it involves 4 loops.

This can be solved in O(n3) time complexity. To be precise you can solve in ( noOfRows * noOfCols^2) time complexity. The idea is to fix the left and right columns one by one and find the maximum sum contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which have maximum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate sun of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left to right in row i. If we apply Kadane’s 1D algorithm on temp[], and get the maximum sum subarray of temp, this maximum sum would be the maximum possible sum with left and right as boundary columns. To get the overall maximum sum, we compare this sum with the maximum sum.

import java.util.Arrays;

public class MaxSumInRectangle {

public int start = 0, finish = 0;

public int maxSubArraySum(int arr[]) {

// initialize sum, maxSum and start

int sum = 0, maxSum = Integer.MIN_VALUE, i;

// needed if sum NEVER becomes less than 0

start = 0;

// Standard Kadane's algorithm. See following link

for (i = 0; i < arr.length; ++i) {

sum += arr[i];

if (sum < 0) {

sum = 0;

start = i + 1;

} else if (sum > maxSum) {

maxSum = sum;

finish = i;

}

}

return maxSum;

}

// The main function that finds maximum sum rectangle in M[][]

public void findMaxSum(int M[][]) {

// Variables to store the final output

int maxSum = 0, finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;

int left, right, i;

int temp[] = new int[M.length];

int sum;

// Set the left column

for (left = 0; left < M[0].length; ++left) {

// Initialize all elements of temp as 0

Arrays.fill(temp, 0);

// Set the right column for the left column set by outer loop

for (right = left; right < M[0].length; ++right) {

// Calculate sum between current left and right for every row

// 'i'

for (i = 0; i < M.length; ++i)

temp[i] += M[i][right];

// Find the maximum sum subarray in temp[]. The kadane()

// function

// also sets values of start and finish. So 'sum' is sum of

// rectangle between (start, left) and (finish, right) which is

// the

// maximum sum with boundary columns strictly as left and right.

sum = maxSubArraySum(temp);

// Compare sum with maximum sum so far. If sum is more, then

// update

// maxSum and other output values

if (sum > maxSum) {

maxSum = sum;

finalLeft = left;

finalRight = right;

finalTop = start;

finalBottom = finish;

}

}

}

// Print final values

System.out.println("(Top, Left) (" + finalTop + "," + finalLeft + ")");

System.out.println("(Bottom, Right) (" + finalBottom + "," + finalRight

+ ")");

System.out.println("Max sum is: " + maxSum);

}

public static void main(String args[]) {

int M[][] = { { 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 },

{ 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 } };

new MaxSumInRectangle().findMaxSum(M);

}

}

## No comments:

Post a Comment