Skip to main content

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
Last updated on by Kalkicode




Comment

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