Largest submatrix with zero sum using dynamic programming
Here given code implementation process.
import java.util.HashMap;
/*
Java Program for
Largest submatrix with zero sum using dynamic programming
*/
public class SubMatrix
{
public void printMatrix(int[][] matrix)
{
int n = matrix.length;
int m = matrix[0].length;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
System.out.print(" " + matrix[i][j]);
}
System.out.print("\n");
}
}
public void zeroSumSubMatrix(int[][] matrix)
{
int n = matrix.length;
int m = matrix[0].length;
// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int auxiliary[] = new int[n];
int[][] prefixSum = new int[n][m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < n; ++i)
{
for (int j = 1; j < m; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for (int one = 0; one < m; ++one)
{
for (int two = one; two < m; ++two)
{
HashMap < Integer, Integer > rowSum =
new HashMap < Integer, Integer > ();
rowSum.put(0, -1);
for (int row = 0; row < n; ++row)
{
if(one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
}
for (int i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.containsKey(sum))
{
int size = (two - one + 1) * (i - rowSum.get(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.put(sum, i);
}
}
}
sum = 0;
}
// Print matrix elements
printMatrix(matrix);
if (maxSize == 0)
{
System.out.print("\n No Result\n");
}
else
{
System.out.print("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
System.out.print(" " + matrix[i][j]);
}
System.out.print("\n");
}
}
}
public static void main(String[] args)
{
SubMatrix task = new SubMatrix();
int[][] matrix = {
{
1 , 10 , -4 , 15 , -5 , 4
},
{
2 , -5 , 4 , 3 , 1 , -5
},
{
3 , -3 , -7 , -3 , 2 , 8
},
{
4 , 1 , -4 , 7 , -8 , 3
},
{
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
// Include header file
#include <iostream>
#include <unordered_map>
#define N 5
#define M 6
using namespace std;
/*
C++ Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
public: void printMatrix(int matrix[N][M])
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
}
void zeroSumSubMatrix(int matrix[N][M])
{
// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int auxiliary[N];
int prefixSum[N][M];
unordered_map < int, int > rowSum;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < N; ++i)
{
for (int j = 1; j < M; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for (int one = 0; one < M; ++one)
{
for (int two = one; two < M; ++two)
{
rowSum[0] = -1;
for (int row = 0; row < N; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
}
for (int i = 0; i < N; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.find(sum) != rowSum.end())
{
int size = (two - one + 1) *(i - rowSum[sum]);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum] + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum[sum] = i;
}
}
}
rowSum.clear();
sum = 0;
}
// Print matrix elements
this->printMatrix(matrix);
if (maxSize == 0)
{
cout << "\n No Result\n";
}
else
{
cout << "\n Resultant Sub Matrix\n";
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
}
}
};
int main()
{
SubMatrix *task = new SubMatrix();
int matrix[N][M] = {
{
1 , 10 , -4 , 15 , -5 , 4
} , {
2 , -5 , 4 , 3 , 1 , -5
} , {
3 , -3 , -7 , -3 , 2 , 8
} , {
4 , 1 , -4 , 7 , -8 , 3
} , {
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task->zeroSumSubMatrix(matrix);
return 0;
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program for
Largest submatrix with zero sum using dynamic programming
*/
public class SubMatrix
{
public void printMatrix(int[,] matrix)
{
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
}
public void zeroSumSubMatrix(int[,] matrix)
{
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int[] auxiliary = new int[n];
int[,] prefixSum = new int[n,m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
prefixSum[i,j] = matrix[i,j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < n; ++i)
{
for (int j = 1; j < m; ++j)
{
prefixSum[i,j] += prefixSum[i,j - 1];
}
}
for (int one = 0; one < m; ++one)
{
for (int two = one; two < m; ++two)
{
Dictionary < int, int > rowSum =
new Dictionary < int, int > ();
rowSum.Add(0, -1);
for (int row = 0; row < n; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row,two] -
prefixSum[row,one - 1];
}
else
{
auxiliary[row] = prefixSum[row,two];
}
}
for (int i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.ContainsKey(sum))
{
int size = (two - one + 1) * (i - rowSum[sum]);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum] + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.Add(sum, i);
}
}
}
sum = 0;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
Console.Write("\n No Result\n");
}
else
{
Console.Write("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
}
}
public static void Main(String[] args)
{
SubMatrix task = new SubMatrix();
int[,] matrix = {
{
1 , 10 , -4 , 15 , -5 , 4
},
{
2 , -5 , 4 , 3 , 1 , -5
},
{
3 , -3 , -7 , -3 , 2 , 8
},
{
4 , 1 , -4 , 7 , -8 , 3
},
{
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
package main
import "fmt"
/*
Go Program for
Largest submatrix with zero sum using dynamic programming
*/
func printMatrix(matrix[][] int) {
var n int = len(matrix)
var m int = len(matrix[0])
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
fmt.Print(" ", matrix[i][j])
}
fmt.Print("\n")
}
}
func zeroSumSubMatrix(matrix[][] int) {
var n int = len(matrix)
var m int = len(matrix[0])
// Resultant column
var c1 int = 0
var c2 int = 0
// Resultant row
var r1 int = 0
var r2 int = 0
var sum int = 0
var maxSize int = 0
var auxiliary = make([] int, n)
var prefixSum = make([][] int, n)
for i := 0; i < n; i++ {
prefixSum[i] = make([]int,m)
}
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
prefixSum[i][j] = matrix[i][j]
}
}
// calculation prefix sum for each row
for i := 0 ; i < n ; i++ {
for j := 1 ; j < m ; j++ {
prefixSum[i][j] += prefixSum[i][j - 1]
}
}
for one := 0 ; one < m ; one++ {
for two := one ; two < m ; two++ {
var rowSum = make(map[int] int)
rowSum[0] = -1
for row := 0 ; row < n ; row++ {
if one > 0 {
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1]
} else {
auxiliary[row] = prefixSum[row][two]
}
}
for i := 0 ; i < n ; i++ {
sum = sum + auxiliary[i]
if _, found := rowSum[sum] ; found {
var size int = (two - one + 1) * (i - rowSum[sum])
if size > maxSize {
maxSize = size
// Get row information
r1 = rowSum[sum] + 1
r2 = i
// Get col information
c1 = one
c2 = two
}
} else {
rowSum[sum] = i
}
}
}
sum = 0
}
// Print matrix elements
printMatrix(matrix)
if maxSize == 0 {
fmt.Print("\n No Result\n")
} else {
fmt.Print("\n Resultant Sub Matrix\n")
// Print resultant submatrix
for i := r1 ; i <= r2 ; i++ {
for j := c1 ; j <= c2 ; j++ {
fmt.Print(" ", matrix[i][j])
}
fmt.Print("\n")
}
}
}
func main() {
var matrix = [][] int {
{1, 10, -4, 15, -5, 4},
{2, -5, 4, 3, 1, -5},
{3, -3 , -7, -3, 2, 8},
{4, 1, -4, 7, -8, 3},
{2, -1, 5, 6, -3, 8}}
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
zeroSumSubMatrix(matrix)
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
<?php
/*
Php Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
public function printMatrix($matrix)
{
$n = count($matrix);
$m = count($matrix[0]);
for ($i = 0; $i < $n; ++$i)
{
for ($j = 0; $j < $m; ++$j)
{
echo(" ".$matrix[$i][$j]);
}
echo("\n");
}
}
public function zeroSumSubMatrix($matrix)
{
$n = count($matrix);
$m = count($matrix[0]);
// Resultant column
$c1 = 0;
$c2 = 0;
// Resultant row
$r1 = 0;
$r2 = 0;
$sum = 0;
$maxSize = 0;
$auxiliary = array_fill(0, $n, 0);
$prefixSum = array_fill(0, $n, array_fill(0, $m, 0));
for ($i = 0; $i < $n; ++$i)
{
for ($j = 0; $j < $m; ++$j)
{
$prefixSum[$i][$j] = $matrix[$i][$j];
}
}
// calculation prefix sum for each row
for ($i = 0; $i < $n; ++$i)
{
for ($j = 1; $j < $m; ++$j)
{
$prefixSum[$i][$j] += $prefixSum[$i][$j - 1];
}
}
for ($one = 0; $one < $m; ++$one)
{
for ($two = $one; $two < $m; ++$two)
{
$rowSum = array();
$rowSum[0] = -1;
for ($row = 0; $row < $n; ++$row)
{
if ($one > 0)
{
$auxiliary[$row] = $prefixSum[$row][$two] -
$prefixSum[$row][$one - 1];
}
else
{
$auxiliary[$row] = $prefixSum[$row][$two];
}
}
for ($i = 0; $i < $n; ++$i)
{
$sum = $sum + $auxiliary[$i];
if (array_key_exists($sum, $rowSum))
{
$size = ($two - $one + 1) * ($i - $rowSum[$sum]);
if ($size > $maxSize)
{
$maxSize = $size;
// Get row information
$r1 = $rowSum[$sum] + 1;
$r2 = $i;
// Get col information
$c1 = $one;
$c2 = $two;
}
}
else
{
$rowSum[$sum] = $i;
}
}
}
$sum = 0;
}
// Print matrix elements
$this->printMatrix($matrix);
if ($maxSize == 0)
{
echo("\n No Result\n");
}
else
{
echo("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for ($i = $r1; $i <= $r2; $i++)
{
for ($j = $c1; $j <= $c2; $j++)
{
echo(" ".$matrix[$i][$j]);
}
echo("\n");
}
}
}
}
function main()
{
$task = new SubMatrix();
$matrix = array(
array(1, 10, -4, 15, -5, 4),
array(2, -5, 4, 3, 1, -5),
array(3, -3, -7, -3, 2, 8),
array(4, 1, -4, 7, -8, 3),
array(2, -1, 5, 6, -3, 8)
);
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
$task->zeroSumSubMatrix($matrix);
}
main();
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
/*
Node JS Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
printMatrix(matrix)
{
var n = matrix.length;
var m = matrix[0].length;
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
zeroSumSubMatrix(matrix)
{
var n = matrix.length;
var m = matrix[0].length;
// Resultant column
var c1 = 0;
var c2 = 0;
// Resultant row
var r1 = 0;
var r2 = 0;
var sum = 0;
var maxSize = 0;
var auxiliary = Array(n).fill(0);
var prefixSum = Array(n).fill(0).map(() => new Array(m).fill(0));
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (var i = 0; i < n; ++i)
{
for (var j = 1; j < m; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for (var one = 0; one < m; ++one)
{
for (var two = one; two < m; ++two)
{
var rowSum = new Map();
rowSum.set(0, -1);
for (var row = 0; row < n; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
}
for (var i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.has(sum))
{
var size = (two - one + 1) * (i - rowSum.get(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.set(sum, i);
}
}
}
sum = 0;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
process.stdout.write("\n No Result\n");
}
else
{
process.stdout.write("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (var i = r1; i <= r2; i++)
{
for (var j = c1; j <= c2; j++)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
}
}
function main()
{
var task = new SubMatrix();
var matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
];
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
main();
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
# Python 3 Program for
# Largest submatrix with zero sum using dynamic programming
class SubMatrix :
def printMatrix(self, matrix) :
n = len(matrix)
m = len(matrix[0])
i = 0
while (i < n) :
j = 0
while (j < m) :
print(" ", matrix[i][j], end = "")
j += 1
print(end = "\n")
i += 1
def zeroSumSubMatrix(self, matrix) :
n = len(matrix)
m = len(matrix[0])
# Resultant column
c1 = 0
c2 = 0
# Resultant row
r1 = 0
r2 = 0
sum = 0
maxSize = 0
auxiliary = [0] * (n)
prefixSum = [[0] * (m) for _ in range(n) ]
i = 0
while (i < n) :
j = 0
while (j < m) :
prefixSum[i][j] = matrix[i][j]
j += 1
i += 1
i = 0
# calculation prefix sum for each row
while (i < n) :
j = 1
while (j < m) :
prefixSum[i][j] += prefixSum[i][j - 1]
j += 1
i += 1
one = 0
while (one < m) :
two = one
while (two < m) :
rowSum = dict()
rowSum[0] = -1
row = 0
while (row < n) :
if (one > 0) :
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1]
else :
auxiliary[row] = prefixSum[row][two]
row += 1
i = 0
while (i < n) :
sum = sum + auxiliary[i]
if ((sum in rowSum.keys())) :
size = (two - one + 1) * (i - rowSum.get(sum))
if (size > maxSize) :
maxSize = size
# Get row information
r1 = rowSum.get(sum) + 1
r2 = i
# Get col information
c1 = one
c2 = two
else :
rowSum[sum] = i
i += 1
two += 1
sum = 0
one += 1
# Print matrix elements
self.printMatrix(matrix)
if (maxSize == 0) :
print("\n No Result")
else :
print("\n Resultant Sub Matrix")
i = r1
# Print resultant submatrix
while (i <= r2) :
j = c1
while (j <= c2) :
print(" ", matrix[i][j], end = "")
j += 1
print(end = "\n")
i += 1
def main() :
task = SubMatrix()
matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
]
# marix =
# [
# [1, 10, -4, 15, -5, 4]
# [2, -5, 4, 3, 1, -5]
# [3, -3 , -7, -3, 2, 8]
# [4, 1, -4, 7, -8, 3]
# [2, -1, 5, 6, -3, 8]
# ]
# -----------------------------------
# Output
# [
# [ 2 -5 4 3 1 -5 ]
# [ 3 -3 -7 -3 2 8 ]
# ]
# Resultant sub matrix
# --------------------------
# 2 + (-5) + 4 + 3 + 1 + (-5) +
# 3 + (-3) + (-7) + (-3) + 2 + 8
# size = 12
# sum = 0
# -----------------------------
task.zeroSumSubMatrix(matrix)
if __name__ == "__main__": main()
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
# Ruby Program for
# Largest submatrix with zero sum using dynamic programming
class SubMatrix
def printMatrix(matrix)
n = matrix.length
m = matrix[0].length
i = 0
while (i < n)
j = 0
while (j < m)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
end
def zeroSumSubMatrix(matrix)
n = matrix.length
m = matrix[0].length
# Resultant column
c1 = 0
c2 = 0
# Resultant row
r1 = 0
r2 = 0
sum = 0
maxSize = 0
auxiliary = Array.new(n) {0}
prefixSum = Array.new(n) {Array.new(m) {0}}
i = 0
while (i < n)
j = 0
while (j < m)
prefixSum[i][j] = matrix[i][j]
j += 1
end
i += 1
end
i = 0
# calculation prefix sum for each row
while (i < n)
j = 1
while (j < m)
prefixSum[i][j] += prefixSum[i][j - 1]
j += 1
end
i += 1
end
one = 0
while (one < m)
two = one
while (two < m)
rowSum = Hash.new()
rowSum[0] = -1
row = 0
while (row < n)
if (one > 0)
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1]
else
auxiliary[row] = prefixSum[row][two]
end
row += 1
end
i = 0
while (i < n)
sum = sum + auxiliary[i]
if (rowSum.key?(sum))
size = (two - one + 1) * (i - rowSum[sum])
if (size > maxSize)
maxSize = size
# Get row information
r1 = rowSum[sum] + 1
r2 = i
# Get col information
c1 = one
c2 = two
end
else
rowSum[sum] = i
end
i += 1
end
two += 1
end
sum = 0
one += 1
end
# Print matrix elements
self.printMatrix(matrix)
if (maxSize == 0)
print("\n No Result\n")
else
print("\n Resultant Sub Matrix\n")
i = r1
# Print resultant submatrix
while (i <= r2)
j = c1
while (j <= c2)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
end
end
end
def main()
task = SubMatrix.new()
matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
]
# marix =
# [
# [1, 10, -4, 15, -5, 4]
# [2, -5, 4, 3, 1, -5]
# [3, -3 , -7, -3, 2, 8]
# [4, 1, -4, 7, -8, 3]
# [2, -1, 5, 6, -3, 8]
# ]
# -----------------------------------
# Output
# [
# [ 2 -5 4 3 1 -5 ]
# [ 3 -3 -7 -3 2 8 ]
# ]
# Resultant sub matrix
# --------------------------
# 2 + (-5) + 4 + 3 + 1 + (-5) +
# 3 + (-3) + (-7) + (-3) + 2 + 8
# size = 12
# sum = 0
# -----------------------------
task.zeroSumSubMatrix(matrix)
end
main()
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
import scala.collection.mutable._;
/*
Scala Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix()
{
def printMatrix(matrix: Array[Array[Int]]): Unit = {
var n: Int = matrix.length;
var m: Int = matrix(0).length;
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
def zeroSumSubMatrix(matrix: Array[Array[Int]]): Unit = {
var n: Int = matrix.length;
var m: Int = matrix(0).length;
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: Array[Int] = Array.fill[Int](n)(0);
var prefixSum: Array[Array[Int]] = Array.fill[Int](n, m)(0);
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum(i)(j) = matrix(i)(j);
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum(i)(j) += prefixSum(i)(j - 1);
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
var rowSum: HashMap[Int, Int] = new HashMap[Int, Int]();
rowSum.addOne(0, -1);
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary(row) = prefixSum(row)(two) -
prefixSum(row)(one - 1);
}
else
{
auxiliary(row) = prefixSum(row)(two);
}
row += 1;
}
var i: Int = 0;
while (i < n)
{
sum = sum + auxiliary(i);
if (rowSum.contains(sum))
{
var size: Int = (two - one + 1) *
(i - rowSum.get(sum).get);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum).get + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.addOne(sum, i);
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result\n");
}
else
{
print("\n Resultant Sub Matrix\n");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubMatrix = new SubMatrix();
var matrix: Array[Array[Int]] = Array(Array(1, 10, -4, 15, -5, 4), Array(2, -5, 4, 3, 1, -5), Array(3, -3, -7, -3, 2, 8), Array(4, 1, -4, 7, -8, 3), Array(2, -1, 5, 6, -3, 8));
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
import Foundation;
/*
Swift 4 Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
func printMatrix(_ matrix: [[Int]])
{
let n: Int = matrix.count;
let m: Int = matrix[0].count;
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
func zeroSumSubMatrix(_ matrix: [[Int]])
{
let n: Int = matrix.count;
let m: Int = matrix[0].count;
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: [Int] = Array(repeating: 0, count: n);
var prefixSum: [[Int]] =
Array(repeating: Array(repeating: 0, count: m), count: n);
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum[i][j] = matrix[i][j];
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum[i][j] += prefixSum[i][j - 1];
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
var rowSum = [Int : Int]();
rowSum[0] = -1;
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
row += 1;
}
i = 0;
while (i < n)
{
sum = sum + auxiliary[i];
if (rowSum.keys.contains(sum))
{
let size: Int = (two - one + 1) * (i - rowSum[sum]!);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum]! + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum[sum] = i;
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
self.printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result");
}
else
{
print("\n Resultant Sub Matrix");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
}
}
func main()
{
let task: SubMatrix = SubMatrix();
let matrix: [
[Int]
] = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
];
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
main();
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
/*
Kotlin Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
fun printMatrix(matrix: Array < Array < Int >> ): Unit
{
val n: Int = matrix.count();
val m: Int = matrix[0].count();
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print(" " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
fun zeroSumSubMatrix(matrix: Array < Array < Int >> ): Unit
{
val n: Int = matrix.count();
val m: Int = matrix[0].count();
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: Array < Int > = Array(n)
{
0
};
var prefixSum: Array < Array < Int >> = Array(n)
{
Array(m)
{
0
}
};
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum[i][j] = matrix[i][j];
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum[i][j] += prefixSum[i][j - 1];
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
val rowSum: HashMap < Int, Int > = HashMap < Int, Int > ();
rowSum.put(0, -1);
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
row += 1;
}
i = 0;
while (i < n)
{
sum = sum + auxiliary[i];
if (rowSum.containsKey(sum))
{
val size: Int = (two - one + 1) *
(i - rowSum.getValue(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.getValue(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.put(sum, i);
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result\n");
}
else
{
print("\n Resultant Sub Matrix\n");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print(" " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val task: SubMatrix = SubMatrix();
val matrix: Array < Array < Int >> = arrayOf(arrayOf(1, 10, -4, 15, -5, 4), arrayOf(2, -5, 4, 3, 1, -5), arrayOf(3, -3, -7, -3, 2, 8), arrayOf(4, 1, -4, 7, -8, 3), arrayOf(2, -1, 5, 6, -3, 8));
/*
marix =
[
[1, 10, -4, 15, -5, 4]
[2, -5, 4, 3, 1, -5]
[3, -3 , -7, -3, 2, 8]
[4, 1, -4, 7, -8, 3]
[2, -1, 5, 6, -3, 8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
Output
1 10 -4 15 -5 4
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
4 1 -4 7 -8 3
2 -1 5 6 -3 8
Resultant Sub Matrix
2 -5 4 3 1 -5
3 -3 -7 -3 2 8
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment