Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

// Cpp program to find maximum sum subarray in // a given 2D vector using Naive Approach…

  1. 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

  2. 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);