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 Kadane's…

  1. User

    // Cpp program to find maximum sum subarray in // a given 2D vector using Kadane's algorithm #include #include #include #include using namespace std;

    // Implementation of Kadane's algorithm for 1D vector int kadane(vector& arr, int& start, int& finish) { int sum = 0; int mx = INT_MIN; finish = -1;

    int localStart = 0;
    
    for (int i = 0; i < arr.size(); ++i) {
        sum += arr[i];
        
        if (sum < 0) {
            sum = 0;
            localStart = i + 1;
        }
        else if (sum > mx) {
            mx = sum;
            start = localStart;
            finish = i;
        }
    }
    
    // If all numbers are negative
    if (finish != -1)
        return mx;
    
    // Special case: when all elements are negative
    mx = arr[0];
    start = finish = 0;
    
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > mx) {
            mx = arr[i];
            start = finish = i;
        }
    }
    return mx;
    

    }

    // Function that finds the maximum sum rectangle void findMaxSum(vector<vector>& mat) { if (mat.empty() || mat[0].empty()) { cout << "The matrix is empty." << endl; return; }

    int rows = mat.size();
    int cols = mat[0].size();
    
    // Variables to store the final output
    int mx = INT_MIN;
    int finalLeft, finalRight, finalTop, finalBottom;
    
    // Temporary array to store the sum of elements for each row
    vector<int> temp(rows, 0);
    int start, finish, sum;
    
    // Set the left boundary of the rectangle
    for (int left = 0; left < cols; ++left) {
      
        // Initialize all elements of temp as 0
        fill(temp.begin(), temp.end(), 0);
    
        // Set the right boundary for the current left
        for (int right = left; right < cols; ++right) {
          
            // Calculate sum between current left and right for every row 'i'
            for (int i = 0; i < rows; ++i)
                temp[i] += mat[i][right];
            sum = kadane(temp, start, finish);
            if (sum > mx) {
                mx = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
    
    // Print the final results
    cout << "(Top, Left) (" << finalTop << ", " << finalLeft << ")" << endl;
    cout << "(Bottom, Right) (" << finalBottom << ", " << finalRight << ")" << endl;
    cout << "Max sum is: " << mx << endl;
    

    }

    int main() {

    // Initialize the 2D vector 'mat'
    vector<vector<int>> mat = { 
        { 1, 2, -1, -4, -20 },
        { -8, -3, 4, 2, 1 },
        { 3, 8, 10, 1, 3 },
        { -4, -1, 1, 7, -6 }
    };
    
    // Call the function to find the maximum sum subarray
    findMaxSum(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 program to find maximum sum subarray in 
    # a given 2D list using Kadane's algorithm
    import sys
    
    # Implementation of Kadane's algorithm for 1D list
    def kadane(arr):
        sum = 0
        mx = -sys.maxsize
        finish = -1
    
        start = 0
        localStart = 0
    
        for i in range(len(arr)):
            sum += arr[i]
    
            if sum < 0:
                sum = 0
                localStart = i + 1
            elif sum > mx:
                mx = sum
                start = localStart
                finish = i
    
        # If all numbers are negative
        if finish != -1:
            return mx, start, finish
    
        # Special case: when all elements are negative
        mx = arr[0]
        start = finish = 0
    
        for i in range(1, len(arr)):
            if arr[i] > mx:
                mx = arr[i]
                start = finish = i
        return mx, start, finish
    
    # Function that finds the maximum sum rectangle
    def findMaxSum(mat):
        if not mat or not mat[0]:
            print("The matrix is empty.")
            return
    
        rows = len(mat)
        cols = len(mat[0])
    
        # Variables to store the final output
        mx = -sys.maxsize
        finalLeft = finalRight = finalTop = finalBottom = 0
    
        # Temporary list to store the sum of elements for each row
        temp = [0] * rows
    
        # Set the left boundary of the rectangle
        for left in range(cols):
          
            # Initialize all elements of temp as 0
            for i in range(rows):
                temp[i] = 0
    
            # Set the right boundary for the current left
            for right in range(left, cols):
              
                # Calculate sum between current left and right for every row 'i'
                for i in range(rows):
                    temp[i] += mat[i][right]
                sum, start, finish = kadane(temp)
                if sum > mx:
                    mx = sum
                    finalLeft = left
                    finalRight = right
                    finalTop = start
                    finalBottom = finish
    
        # Print the final results
        print("(Top, Left) (", finalTop, ",", finalLeft, ")")
        print("(Bottom, Right) (", finalBottom, ",", finalRight, ")")
        print("Max sum is:", mx)
    
    # Initialize the 2D list 'mat'
    mat = [ 
        [ 1, 2, -1, -4, -20 ],
        [ -8, -3, 4, 2, 1 ],
        [ 3, 8, 10, 1, 3 ],
        [ -4, -1, 1, 7, -6 ]
    ]
    
    # Call the function to find the maximum sum subarray
    findMaxSum(mat)
    
    // Java program to find maximum sum subarray in 
    // a given 2D vector using Kadane's algorithm
    import java.util.*;
    
    class GfG {
    
        // Implementation of Kadane's algorithm for 1D list
        static int[] kadane(int[] arr) {
            int sum = 0;
            int mx = Integer.MIN_VALUE;
            int finish = -1;
    
            int start = 0;
            int localStart = 0;
    
            for (int i = 0; i < arr.length; i++) {
                sum += arr[i];
    
                if (sum < 0) {
                    sum = 0;
                    localStart = i + 1;
                }
                else if (sum > mx) {
                    mx = sum;
                    start = localStart;
                    finish = i;
                }
            }
    
            // If all numbers are negative
            if (finish != -1)
                return new int[]{mx, start, finish};
    
            // Special case: when all elements are negative
            mx = arr[0];
            start = finish = 0;
    
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > mx) {
                    mx = arr[i];
                    start = finish = i;
                }
            }
            return new int[]{mx, start, finish};
        }
    
        // Function that finds the maximum sum rectangle
        static void findMaxSum(int[][] mat) {
            if (mat.length == 0 || mat[0].length == 0) {
                System.out.println("The matrix is empty.");
                return;
            }
    
            int rows = mat.length;
            int cols = mat[0].length;
    
            // Variables to store the final output
            int mx = Integer.MIN_VALUE;
            int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;
    
            // Temporary array to store the sum of elements for each row
            int[] temp = new int[rows];
            int[] kadaneResult;
    
            // Set the left boundary of the rectangle
            for (int left = 0; left < cols; left++) {
              
                // Initialize all elements of temp as 0
                Arrays.fill(temp, 0);
    
                // Set the right boundary for the current left
                for (int right = left; right < cols; right++) {
                  
                    // Calculate sum between current left and right for every row 'i'
                    for (int i = 0; i < rows; i++)
                        temp[i] += mat[i][right];
                    kadaneResult = kadane(temp);
                    int sum = kadaneResult[0];
                    int start = kadaneResult[1];
                    int finish = kadaneResult[2];
                    if (sum > mx) {
                        mx = sum;
                        finalLeft = left;
                        finalRight = right;
                        finalTop = start;
                        finalBottom = finish;
                    }
                }
            }
    
            // Print the final results
            System.out.println("(Top, Left) (" + finalTop + ", " + finalLeft + ")");
            System.out.println("(Bottom, Right) (" + finalBottom + ", " + finalRight + ")");
            System.out.println("Max sum is: " + mx);
        }
    
        public static void main(String[] args) {
          
            // Initialize the 2D array 'mat'
            int[][] mat = { 
                { 1, 2, -1, -4, -20 },
                { -8, -3, 4, 2, 1 },
                { 3, 8, 10, 1, 3 },
                { -4, -1, 1, 7, -6 }
            };
    
            // Call the function to find the maximum sum subarray
            findMaxSum(mat);
        }
    }
    
    // C# program to find maximum sum subarray in 
    // a given 2D list using Kadane's algorithm
    using System;
    using System.Collections.Generic;
    
    class GfG
    {
        // Implementation of Kadane's algorithm for 1D list
        static int[] Kadane(List<int> arr)
        {
            int sum = 0;
            int mx = int.MinValue;
            int finish = -1;
    
            int start = 0;
            int localStart = 0;
    
            for (int i = 0; i < arr.Count; i++)
            {
                sum += arr[i];
    
                if (sum < 0)
                {
                    sum = 0;
                    localStart = i + 1;
                }
                else if (sum > mx)
                {
                    mx = sum;
                    start = localStart;
                    finish = i;
                }
            }
    
            // If all numbers are negative
            if (finish != -1)
                return new int[] { mx, start, finish };
    
            // Special case: when all elements are negative
            mx = arr[0];
            start = finish = 0;
    
            for (int i = 1; i < arr.Count; i++)
            {
                if (arr[i] > mx)
                {
                    mx = arr[i];
                    start = finish = i;
                }
            }
            return new int[] { mx, start, finish };
        }
    
        // Function that finds the maximum sum rectangle
        static void FindMaxSum(int[][] mat)
        {
            if (mat.Length == 0 || mat[0].Length == 0)
            {
                Console.WriteLine("The matrix is empty.");
                return;
            }
    
            int rows = mat.Length;
            int cols = mat[0].Length;
    
            // Variables to store the final output
            int mx = int.MinValue;
            int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;
    
            // Temporary list to store the sum of elements for each row
            List<int> temp = new List<int>(new int[rows]);
            int[] kadaneResult;
    
            // Set the left boundary of the rectangle
            for (int left = 0; left < cols; left++)
            {
              
                // Initialize all elements of temp as 0
                for (int i = 0; i < rows; i++)
                    temp[i] = 0;
    
                // Set the right boundary for the current left
                for (int right = left; right < cols; right++)
                {
                  
                    // Calculate sum between current left and right for every row 'i'
                    for (int i = 0; i < rows; i++)
                        temp[i] += mat[i][right];
                    kadaneResult = Kadane(temp);
                    int sum = kadaneResult[0];
                    int start = kadaneResult[1];
                    int finish = kadaneResult[2];
                    if (sum > mx)
                    {
                        mx = sum;
                        finalLeft = left;
                        finalRight = right;
                        finalTop = start;
                        finalBottom = finish;
                    }
                }
            }
    
            // Print the final results
            Console.WriteLine("(Top, Left) (" + finalTop + ", " + finalLeft + ")");
            Console.WriteLine("(Bottom, Right) (" + finalBottom + ", " + finalRight + ")");
            Console.WriteLine("Max sum is: " + mx);
        }
    
        static void Main(string[] args)
        {
          
            // Initialize the 2D array 'mat'
            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 }
            };
    
            // Call the function to find the maximum sum subarray
            FindMaxSum(mat);
        }
    }
    
    // JavaScript program to find maximum sum subarray in 
    // a given 2D array using Kadane's algorithm
    
    // Implementation of Kadane's algorithm for 1D array
    function kadane(arr) {
        let sum = 0;
        let mx = Number.MIN_SAFE_INTEGER;
        let finish = -1;
    
        let start = 0;
        let localStart = 0;
    
        for (let i = 0; i < arr.length; i++) {
            sum += arr[i];
    
            if (sum < 0) {
                sum = 0;
                localStart = i + 1;
            }
            else if (sum > mx) {
                mx = sum;
                start = localStart;
                finish = i;
            }
        }
    
        // If all numbers are negative
        if (finish !== -1)
            return [mx, start, finish];
    
        // Special case: when all elements are negative
        mx = arr[0];
        start = finish = 0;
    
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] > mx) {
                mx = arr[i];
                start = finish = i;
            }
        }
        return [mx, start, finish];
    }
    
    // Function that finds the maximum sum rectangle
    function findMaxSum(mat) {
        if (mat.length === 0 || mat[0].length === 0) {
            console.log("The matrix is empty.");
            return;
        }
    
        let rows = mat.length;
        let cols = mat[0].length;
    
        // Variables to store the final output
        let mx = Number.MIN_SAFE_INTEGER;
        let finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;
    
        // Temporary array to store the sum of elements for each row
        let temp = new Array(rows).fill(0);
        let sum, start, finish;
    
        // Set the left boundary of the rectangle
        for (let left = 0; left < cols; left++) {
          
            // Initialize all elements of temp as 0
            temp.fill(0);
    
            // Set the right boundary for the current left
            for (let right = left; right < cols; right++) {
              
                // Calculate sum between current left and right for every row 'i'
                for (let i = 0; i < rows; i++)
                    temp[i] += mat[i][right];
                let result = kadane(temp);
                sum = result[0];
                start = result[1];
                finish = result[2];
                if (sum > mx) {
                    mx = sum;
                    finalLeft = left;
                    finalRight = right;
                    finalTop = start;
                    finalBottom = finish;
                }
            }
        }
    
        // Print the final results
        console.log(`(Top, Left) (${finalTop}, ${finalLeft})`);
        console.log(`(Bottom, Right) (${finalBottom}, ${finalRight})`);
        console.log(`Max sum is: ${mx}`);
    }
    
    // Initialize the 2D array 'mat'
    let mat = [ 
        [ 1, 2, -1, -4, -20 ],
        [ -8, -3, 4, 2, 1 ],
        [ 3, 8, 10, 1, 3 ],
        [ -4, -1, 1, 7, -6 ]
    ];
    
    // Call the function to find the maximum sum subarray
    findMaxSum(mat);