Find max sum of SubMatrix 3x3 JavaScript

find maximum sum submatrix in a given matrix python
find all submatrix of a matrix python
minimum sum submatrix in a given 2d array
submatrix sum
maximum sum square sub-matrix in c
sum of submatrix leetcode
largest rectangular sub matrix whose sum is 0
submatrix sum equal to k

I practice work with matrix but I stuck here. I need to find max sum of subMatrix.

const matrix = [ 
    [ 1,  1,  3,  3,  5],
    [-6, -7,  2, -3, -1],
    [ 3,  0, -4,  5,  9],
    [ 7, -7,  0,  1,  0],
    [-7, -6, -4, -4,  9],
]

The current matrix is 5x5. I need to find the maxSum of 3x3 sub matrixes. So the maxSum here is 19. I highlight here the submatrix having this sum:

            +----------+
     1   1  |  3  3  5 | 
    -6  -7  |  2 -3 -1 | 
     3   0  | -4  5  9 | 
            +----------+
     7  -7     0  1  0
    -7  -6    -4 -4  9

The script should be working with bigger matrix. I need help I can't make it iterate properly over each 3x3 matrix.

const subLength = 3 * 3;
let maxSum = 0;
for (let subMatrix = 0; subMatrix < subLength; subMatrix++) {
    let sum = 0;
    for (let rows = 0; rows < 3; rows++) {
        for (let cols = subMatrix; cols < matrix.length; cols++) {
            sum += matrix[rows][cols];
        }
    }
    if (maxSum < sum) {
        maxSum = sum;
    }
}
console.log(maxSum);

The code works fine with that matrix but not with another and I know the problem is in the third nested loop and probably, something in the first. In the third I have to iterate from 0 to 3 next from 1 to (3 + 1), from (3 + 2) and moving on next array on the second row and start from zero again.

Can you fix my code ?

It will be easier if you replace your outer loop with two outer loops: one for what the first row will be of the submatrix, and another for its first column. Then the two inner loops should iterate over the 3 rows and 3 columns of the submatrix that starts there.

Here is your code with minimal changes:

function maxSubSum(matrix, subLength) {
    let maxSum = 0;

    for (let firstRow = 0; firstRow <= matrix.length - subLength; firstRow++) {
        for (let firstCol = 0; firstCol <= matrix[0].length - subLength; firstCol++) {
            let sum = 0;
            for (let row = 0; row < 3; row++) {
                for (let col = 0; col < 3; col++) {
                    sum += matrix[firstRow+row][firstCol+col];
                }
            }
            if (maxSum < sum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

const matrix = [ 
    [ 1,  1,  3,  3,  5],
    [-6, -7,  2, -3, -1],
    [ 3,  0, -4,  5,  9],
    [ 7, -7,  0,  1,  0],
    [-7, -6, -4, -4,  9],
];

console.log(maxSubSum(matrix, 3));

matrix - Find max sum of SubMatrix 3x3 JavaScript, It will be easier if you replace your outer loop with two outer loops: one for what the first row will be of the submatrix, and another for its first  Given a M x N matrix, calculate maximum sum submatrix of size k x k in a given M x N matrix in O(M*N) time. For example, consider below 5 x 5 matrix.. The idea is to pre-process the matrix. We take an auxiliary matrix sum[][] where sum[i][j] will store the sum of the elements in matrix from (0, 0) to (i, j).

You could create a function with reduce method that takes col and row params and slice them from original arrays but for inner array you just reverse the element order.

const matrix = [
  [1, 1, 3, 3, 5],
  [-6, -7, 2, -3, -1],
  [3, 0, -4, 5, 9],
  [7, -7, 0, 1, 0],
  [-7, -6, -4, -4, 9, 11, 40],
]

function sum(matrix, row, col) {
  return matrix.slice(0, row).reduce((r, e) => {
    [...e].reverse().slice(0, col).forEach(c => r += c)
    return r;
  }, 0)
}

console.log(sum(matrix, 3, 3))

Print maximum sum square sub-matrix of given size, Java, Java Programs, Java Quiz, JavaScript, JQuery, JS++, Julia, Kotlin, Linked List, Linux-Unix Given an N x N matrix, find a k x k submatrix where k <= N and k >= 1, such that sum of all the elements in submatrix is maximum. An efficient C++ program to find maximum sum cout << "Maximum sum 3 x 3 matrix is\n" ;. The task is to find maximum length of a square submatrix having sum of elements less than or equal to K or print 0 if no such square exits. Examples: Input: r = 4, c = 4 , k = 6 matrix[][] = { {1, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, } Output: 3 Explanation: Square from (0,0) to (2,2) with sum 5 is one of the valid answer.

You could get a part of the matrix first and then get the sum of the sub matrix.

const
    matrix = [[1, 1, 3, 3, 5], [-6, -7, 2, -3, -1], [3, 0, -4, 5, 9], [7, -7, 0, 1, 0], [-7, -6, -4, -4, 9, 11, 40]],
    cols = 3,
    rows = 3,
    left = -3,
    top_ = 0,                                   // top is a reserved property of windows
    sum = matrix
        .slice(top_, top_ >= 0 ? rows : undefined)
        .map(a => a.slice(left, left >= 0 ? cols : undefined))
        .reduce((r, a) => a.reduce((s, v) => s + v, r), 0);

console.log(sum);

Find Maximum Sum Submatrix in a given matrix, Given a M x N matrix, calculate maximum sum submatrix of size k x k in a given M x N Calculate sum of all elements in a sub-matrix in constant time Java, Python, JavaScript, C#, PHP and many more popular programming languages. Given an N x N matrix, find a k x k submatrix where k <= N and k >= 1, such that sum of all the elements in submatrix is maximum. The input matrix can contain zero, positive and negative numbers. For example consider below matrix, if k = 3, then output should print the sub-matrix enclosed in blue.

Submatrix with largest sum, Find submatrix with largest sum in a given 2D matrix of integers. Solution: Before Kadane's algorithm finds sub-array with maximum sum in O(n) for 1D arrays. 1. Given a M x N matrix, find sum of all K x K sub-matrix. 2. Given a M x N matrix and a cell (i, j), find sum of all elements of the matrix in constant time except the elements present at row i & column j of the matrix. Related Problems: Find Maximum Sum Submatrix in a given matrix

Maximum Sum Rectangular Submatrix in Matrix dynamic , Find maximum sum rectangle in 2D matrix. https://www.facebook.com/​tusharroy25 Duration: 13:54 Posted: May 4, 2015 Given a matrix of size M x N, there are large number of queries to find submatrix sums. Inputs to queries are left top and right bottom indexes of submatrix whose sum is to find out. How to preprocess the matrix so that submatrix sum queries can be performed in O(1) time. Example :

Maximum Sum of Subarray problem, And here, to find the maximum sum contiguous subarray, we would run two loops​. The outer loop picks the beginning element, the inner loop  We are given a matrix of N * M. To find max path sum first we have to find max value in first row of matrix. Store this value in res. Now for every element in matrix update element with max value which can be included in max path. If the value is greater then res then update res. In last return res which consists of max path sum value.

Comments
  • Why does your matrix have 7 values in its last row?
  • thanks I fixed it.
  • It works with 9 of 12 cases. 3 cases gives me wrong answer and return 0. May be I missed something in the question. Can you check ? Here is my task. I have the size of matrix judge.telerikacademy.com/problem/27maxsuminmatrix
  • I had assumed that matrix was square, but it turns out to be rectangular. See the update of the script.