// Cpp program to find maximum sum subarray in // a given 2D vector using Naive Approach…
- User
// Cpp program to find maximum sum subarray in // a given 2D vector using Naive Approach #include #include #include using namespace std;
// Function that finds the maximum sum rectangle void maxMatrixSum(vector<vector >& mat) { int n = mat.size(); int m = mat[0].size(); int maxSum = INT_MIN; int top = 0, bottom = 0, left = 0, right = 0;
// a loop for top row position in the rectangle for (int i = 0; i < n; i++) { // a loop for left column position of the rectangle for (int j = 0; j < m; j++) { // a loop for bottom row in the rectangle for (int k = i; k < n; k++) { // a loop for right column in the rectangle for (int l = j; l < m; l++) { int curr = 0; // Calculate sum of the current rectangle for (int x = i; x <= k; x++) { for (int y = j; y <= l; y++) { curr += mat[x][y]; } } // Update the resultant variables if curr > maxSum if (curr > maxSum) { maxSum = curr; top = i; left = j; bottom = k; right = l; } } } } } cout << "( Top , Left ) = ( " << top << " , " << left << " )" << endl; cout << "( Bottom , Right ) = ( " << bottom << " , " << right << " )" << endl; cout << "The sum of this rectangle is: " << maxSum << endl;}
int main() { vector<vector > mat = { { 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 } }; maxMatrixSum(mat); return 0; }
Give me code in Python, Java, C#, JavaScript
Remember like Cpp is for C++ and at start replace Cpp with language name and then comment
without changing variable name and also do not change comments
have one line space after code when comment is written.
don’t use class if needed then name it GfG
don’t use public if not needed.
If main class is not needed don’t use it like in python and JavaScript
and In C program don’t use #define and malloc and calloc instead use simple array
- Assistant
# Python import sys # Function that finds the maximum sum rectangle def maxMatrixSum(mat): n = len(mat) m = len(mat[0]) maxSum = -sys.maxsize top = 0 bottom = 0 left = 0 right = 0 # a loop for top row position in the rectangle for i in range(n): # a loop for left column position of the rectangle for j in range(m): # a loop for bottom row in the rectangle for k in range(i, n): # a loop for right column in the rectangle for l in range(j, m): curr = 0 # Calculate sum of the current rectangle for x in range(i, k + 1): for y in range(j, l + 1): curr += mat[x][y] # Update the resultant variables if curr > maxSum if curr > maxSum: maxSum = curr top = i left = j bottom = k right = l print(f"( Top , Left ) = ( {top} , {left} )") print(f"( Bottom , Right ) = ( {bottom} , {right} )") print(f"The sum of this rectangle is: {maxSum}") mat = [ [1, 2, -1, -4, -20], [-8, -3, 4, 2, 1], [3, 8, 10, 1, 3], [-4, -1, 1, 7, -6] ] maxMatrixSum(mat)// Java import java.util.*; class GfG { // Function that finds the maximum sum rectangle static void maxMatrixSum(int[][] mat) { int n = mat.length; int m = mat[0].length; int maxSum = Integer.MIN_VALUE; int top = 0, bottom = 0, left = 0, right = 0; // a loop for top row position in the rectangle for (int i = 0; i < n; i++) { // a loop for left column position of the rectangle for (int j = 0; j < m; j++) { // a loop for bottom row in the rectangle for (int k = i; k < n; k++) { // a loop for right column in the rectangle for (int l = j; l < m; l++) { int curr = 0; // Calculate sum of the current rectangle for (int x = i; x <= k; x++) { for (int y = j; y <= l; y++) { curr += mat[x][y]; } } // Update the resultant variables if curr > maxSum if (curr > maxSum) { maxSum = curr; top = i; left = j; bottom = k; right = l; } } } } } System.out.println("( Top , Left ) = ( " + top + " , " + left + " )"); System.out.println("( Bottom , Right ) = ( " + bottom + " , " + right + " )"); System.out.println("The sum of this rectangle is: " + maxSum); } public static void main(String[] args) { int[][] mat = { { 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 } }; maxMatrixSum(mat); } }// C# using System; class GfG { // Function that finds the maximum sum rectangle static void maxMatrixSum(int[][] mat) { int n = mat.Length; int m = mat[0].Length; int maxSum = int.MinValue; int top = 0, bottom = 0, left = 0, right = 0; // a loop for top row position in the rectangle for (int i = 0; i < n; i++) { // a loop for left column position of the rectangle for (int j = 0; j < m; j++) { // a loop for bottom row in the rectangle for (int k = i; k < n; k++) { // a loop for right column in the rectangle for (int l = j; l < m; l++) { int curr = 0; // Calculate sum of the current rectangle for (int x = i; x <= k; x++) { for (int y = j; y <= l; y++) { curr += mat[x][y]; } } // Update the resultant variables if curr > maxSum if (curr > maxSum) { maxSum = curr; top = i; left = j; bottom = k; right = l; } } } } } Console.WriteLine($"( Top , Left ) = ( {top} , {left} )"); Console.WriteLine($"( Bottom , Right ) = ( {bottom} , {right} )"); Console.WriteLine($"The sum of this rectangle is: {maxSum}"); } static void Main(string[] args) { int[][] mat = new int[][] { new int[] { 1, 2, -1, -4, -20 }, new int[] { -8, -3, 4, 2, 1 }, new int[] { 3, 8, 10, 1, 3 }, new int[] { -4, -1, 1, 7, -6 } }; maxMatrixSum(mat); } }// JavaScript // Function that finds the maximum sum rectangle function maxMatrixSum(mat) { let n = mat.length; let m = mat[0].length; let maxSum = Number.MIN_SAFE_INTEGER; let top = 0, bottom = 0, left = 0, right = 0; // a loop for top row position in the rectangle for (let i = 0; i < n; i++) { // a loop for left column position of the rectangle for (let j = 0; j < m; j++) { // a loop for bottom row in the rectangle for (let k = i; k < n; k++) { // a loop for right column in the rectangle for (let l = j; l < m; l++) { let curr = 0; // Calculate sum of the current rectangle for (let x = i; x <= k; x++) { for (let y = j; y <= l; y++) { curr += mat[x][y]; } } // Update the resultant variables if curr > maxSum if (curr > maxSum) { maxSum = curr; top = i; left = j; bottom = k; right = l; } } } } } console.log(`( Top , Left ) = ( ${top} , ${left} )`); console.log(`( Bottom , Right ) = ( ${bottom} , ${right} )`); console.log(`The sum of this rectangle is: ${maxSum}`); } const mat = [ [1, 2, -1, -4, -20], [-8, -3, 4, 2, 1], [3, 8, 10, 1, 3], [-4, -1, 1, 7, -6] ]; maxMatrixSum(mat);