Maximum prefix sum in 2d array
Here given code implementation process.
/*
Java program for
Maximum prefix sum in 2d array
*/
public class PrefixSum
{
// Display matrix elements
public void printMatrix(int[][] matrix)
{
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
System.out.print(" " + matrix[i][j]);
}
System.out.print("\n");
}
}
public void changeByPrefixSum(int[][] matrix)
{
int row = matrix.length;
int col = matrix[0].length;
// Change element of first row
// By sum of previous element
for (int i = 1; i < row; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < col; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (int i = 1; i < row; ++i)
{
for (int j = 1; j < col; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
public static void main(String[] args)
{
PrefixSum task = new PrefixSum();
int[][] matrix = {
{
1 , 4 , 3 , 7 , 2
},
{
2 , 4 , 3 , 8 , 3
},
{
4 , 1 , 6 , 7 , 1
},
{
5 , 4 , 3 , 7 , 12
},
{
1 , 5 , 10 , 1 , 2
}
};
task.printMatrix(matrix);
task.changeByPrefixSum(matrix);
System.out.print("\n ");
task.printMatrix(matrix);
}
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
// Include header file
#include <iostream>
#define R 5
#define C 5
using namespace std;
/*
C++ program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
public:
// Display matrix elements
void printMatrix(int matrix[R][C])
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
}
void changeByPrefixSum(int matrix[R][C])
{
// Change element of first row
// By sum of previous element
for (int i = 1; i < R; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < C; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (int i = 1; i < R; ++i)
{
for (int j = 1; j < C; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
};
int main()
{
PrefixSum *task = new PrefixSum();
int matrix[R][C] = {
{1, 4, 3, 7, 2},
{2, 4, 3, 8, 3},
{4, 1, 6, 7, 1},
{5, 4, 3, 7, 12},
{1, 5, 10, 1, 2}
};
task->printMatrix(matrix);
task->changeByPrefixSum(matrix);
cout << "\n ";
task->printMatrix(matrix);
return 0;
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
// Include namespace system
using System;
/*
Csharp program for
Maximum prefix sum in 2d array
*/
public class PrefixSum
{
// Display matrix elements
public void printMatrix(int[,] matrix)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
}
public void changeByPrefixSum(int[,] matrix)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
// Change element of first row
// By sum of previous element
for (int i = 1; i < row; ++i)
{
matrix[i,0] = matrix[i - 1,0] + matrix[i,0];
}
// Change element of first column
// By sum of previous element
for (int i = 1; i < col; ++i)
{
matrix[0,i] = matrix[0,i - 1] + matrix[0,i];
}
// Change remaining elements
for (int i = 1; i < col; ++i)
{
for (int j = 1; j < col; ++j)
{
matrix[i,j] = matrix[i - 1,j] + matrix[i,j - 1] -
matrix[i - 1,j - 1] + matrix[i,j];
}
}
}
public static void Main(String[] args)
{
PrefixSum task = new PrefixSum();
int[,] matrix = {
{
1 , 4 , 3 , 7 , 2
},
{
2 , 4 , 3 , 8 , 3
},
{
4 , 1 , 6 , 7 , 1
},
{
5 , 4 , 3 , 7 , 12
},
{
1 , 5 , 10 , 1 , 2
}
};
task.printMatrix(matrix);
task.changeByPrefixSum(matrix);
Console.Write("\n ");
task.printMatrix(matrix);
}
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
package main
import "fmt"
/*
Go program for
Maximum prefix sum in 2d array
*/
// Display matrix elements
func printMatrix(matrix[][] int) {
var row int = len(matrix)
var col int = len(matrix[0])
for i := 0 ; i < row ; i++ {
for j := 0 ; j < col ; j++ {
fmt.Print(" ", matrix[i][j])
}
fmt.Print("\n")
}
}
func changeByPrefixSum(matrix[][] int) {
var row int = len(matrix)
var col int = len(matrix[0])
// Change element of first row
// By sum of previous element
for i := 1 ; i < row ; i++ {
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
}
// Change element of first column
// By sum of previous element
for i := 1 ; i < col ; i++ {
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
}
// Change remaining elements
for i := 1 ; i < col ; i++ {
for j := 1 ; j < col ; j++ {
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j]
}
}
}
func main() {
var matrix = [][] int {
{1, 4, 3, 7, 2},
{2, 4, 3, 8, 3},
{4, 1, 6, 7, 1},
{5, 4, 3, 7, 12},
{1, 5, 10, 1, 2}}
printMatrix(matrix)
changeByPrefixSum(matrix)
fmt.Print("\n ")
printMatrix(matrix)
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
<?php
/*
Php program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
public function printMatrix($matrix)
{
$row = count($matrix);
$col = count($matrix[0]);
for ($i = 0; $i < $row; $i++)
{
for ($j = 0; $j < $col; $j++)
{
echo(" ".$matrix[$i][$j]);
}
echo("\n");
}
}
public function changeByPrefixSum(&$matrix)
{
$row = count($matrix);
$col = count($matrix[0]);
// Change element of first row
// By sum of previous element
for ($i = 1; $i < $row; ++$i)
{
$matrix[$i][0] = $matrix[$i - 1][0] + $matrix[$i][0];
}
// Change element of first column
// By sum of previous element
for ($i = 1; $i < $col; ++$i)
{
$matrix[0][$i] = $matrix[0][$i - 1] + $matrix[0][$i];
}
// Change remaining elements
for ($i = 1; $i < $col; ++$i)
{
for ($j = 1; $j < $col; ++$j)
{
$matrix[$i][$j] = $matrix[$i - 1][$j] + $matrix[$i][$j - 1] -
$matrix[$i - 1][$j - 1] + $matrix[$i][$j];
}
}
}
}
function main()
{
$task = new PrefixSum();
$matrix = array(
array(1, 4, 3, 7, 2),
array(2, 4, 3, 8, 3),
array(4, 1, 6, 7, 1),
array(5, 4, 3, 7, 12),
array(1, 5, 10, 1, 2)
);
$task->printMatrix($matrix);
$task->changeByPrefixSum($matrix);
echo("\n ");
$task->printMatrix($matrix);
}
main();
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
/*
Node JS program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
printMatrix(matrix)
{
var row = matrix.length;
var col = matrix[0].length;
for (var i = 0; i < row; i++)
{
for (var j = 0; j < col; j++)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
changeByPrefixSum(matrix)
{
var row = matrix.length;
var col = matrix[0].length;
// Change element of first row
// By sum of previous element
for (var i = 1; i < row; ++i)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
}
// Change element of first column
// By sum of previous element
for (var i = 1; i < col; ++i)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
}
// Change remaining elements
for (var i = 1; i < col; ++i)
{
for (var j = 1; j < col; ++j)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
}
}
}
}
function main()
{
var task = new PrefixSum();
var matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
];
task.printMatrix(matrix);
task.changeByPrefixSum(matrix);
process.stdout.write("\n ");
task.printMatrix(matrix);
}
main();
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
# Python 3 program for
# Maximum prefix sum in 2d array
class PrefixSum :
# Display matrix elements
def printMatrix(self, matrix) :
row = len(matrix)
col = len(matrix[0])
i = 0
while (i < row) :
j = 0
while (j < col) :
print(" ", matrix[i][j], end = "")
j += 1
print(end = "\n")
i += 1
def changeByPrefixSum(self, matrix) :
row = len(matrix)
col = len(matrix[0])
i = 1
# Change element of first row
# By sum of previous element
while (i < row) :
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
i += 1
i = 1
# Change element of first column
# By sum of previous element
while (i < col) :
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
i += 1
i = 1
# Change remaining elements
while (i < col) :
j = 1
while (j < col) :
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1] + matrix[i][j]
j += 1
i += 1
def main() :
task = PrefixSum()
matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
]
task.printMatrix(matrix)
task.changeByPrefixSum(matrix)
print("\n ", end = "")
task.printMatrix(matrix)
if __name__ == "__main__": main()
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
# Ruby program for
# Maximum prefix sum in 2d array
class PrefixSum
# Display matrix elements
def printMatrix(matrix)
row = matrix.length
col = matrix[0].length
i = 0
while (i < row)
j = 0
while (j < col)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
end
def changeByPrefixSum(matrix)
row = matrix.length
col = matrix[0].length
i = 1
# Change element of first row
# By sum of previous element
while (i < row)
matrix[i][0] = matrix[i - 1][0] + matrix[i][0]
i += 1
end
i = 1
# Change element of first column
# By sum of previous element
while (i < col)
matrix[0][i] = matrix[0][i - 1] + matrix[0][i]
i += 1
end
i = 1
# Change remaining elements
while (i < col)
j = 1
while (j < col)
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j]
j += 1
end
i += 1
end
end
end
def main()
task = PrefixSum.new()
matrix = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
]
task.printMatrix(matrix)
task.changeByPrefixSum(matrix)
print("\n ")
task.printMatrix(matrix)
end
main()
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
/*
Scala program for
Maximum prefix sum in 2d array
*/
class PrefixSum()
{
// Display matrix elements
def printMatrix(matrix: Array[Array[Int]]): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
def changeByPrefixSum(matrix: Array[Array[Int]]): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix(i)(0) = matrix(i - 1)(0) + matrix(i)(0);
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix(0)(i) = matrix(0)(i - 1) + matrix(0)(i);
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix(i)(j) = matrix(i - 1)(j) + matrix(i)(j - 1) -
matrix(i - 1)(j - 1) + matrix(i)(j);
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PrefixSum = new PrefixSum();
var matrix: Array[Array[Int]] = Array(
Array(1, 4, 3, 7, 2),
Array(2, 4, 3, 8, 3),
Array(4, 1, 6, 7, 1),
Array(5, 4, 3, 7, 12),
Array(1, 5, 10, 1, 2)
);
task.printMatrix(matrix);
task.changeByPrefixSum(matrix);
print("\n ");
task.printMatrix(matrix);
}
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
import Foundation;
/*
Swift 4 program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
func printMatrix(_ matrix: [
[Int]
])
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
func changeByPrefixSum(_ matrix: inout[
[Int]
])
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
j += 1;
}
i += 1;
}
}
}
func main()
{
let task: PrefixSum = PrefixSum();
var matrix: [
[Int]
] = [
[1, 4, 3, 7, 2],
[2, 4, 3, 8, 3],
[4, 1, 6, 7, 1],
[5, 4, 3, 7, 12],
[1, 5, 10, 1, 2]
];
task.printMatrix(matrix);
task.changeByPrefixSum(&matrix);
print("\n ", terminator: "");
task.printMatrix(matrix);
}
main();
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
/*
Kotlin program for
Maximum prefix sum in 2d array
*/
class PrefixSum
{
// Display matrix elements
fun printMatrix(matrix: Array < Array < Int >> ): Unit
{
val row: Int = matrix.count();
val col: Int = matrix[0].count();
var i: Int = 0;
while (i < row)
{
var j: Int = 0;
while (j < col)
{
print(" " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
fun changeByPrefixSum(matrix: Array < Array < Int >> ): Unit
{
val row: Int = matrix.count();
val col: Int = matrix[0].count();
var i: Int = 1;
// Change element of first row
// By sum of previous element
while (i < row)
{
matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
i += 1;
}
i = 1;
// Change element of first column
// By sum of previous element
while (i < col)
{
matrix[0][i] = matrix[0][i - 1] + matrix[0][i];
i += 1;
}
i = 1;
// Change remaining elements
while (i < col)
{
var j: Int = 1;
while (j < col)
{
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] -
matrix[i - 1][j - 1] + matrix[i][j];
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: PrefixSum = PrefixSum();
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(1, 4, 3, 7, 2),
arrayOf(2, 4, 3, 8, 3),
arrayOf(4, 1, 6, 7, 1),
arrayOf(5, 4, 3, 7, 12),
arrayOf(1, 5, 10, 1, 2)
);
task.printMatrix(matrix);
task.changeByPrefixSum(matrix);
print("\n ");
task.printMatrix(matrix);
}
Output
1 4 3 7 2
2 4 3 8 3
4 1 6 7 1
5 4 3 7 12
1 5 10 1 2
1 5 8 15 17
3 11 17 32 37
7 16 28 50 56
12 25 40 69 87
13 31 56 86 106
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