// Cpp program to find maximum sum subarray in // a given 2D vector using Kadane's…
- 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
- 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);