Results 1 to 3 of 3

Thread: How to find submatix with max sum

  1. #1

    How to find submatix with max sum

    How to find submatix with max sum

  2. #2
    Junior Member
    Join Date
    Jul 2007

    Re: How to find submatix with max sum

    Quote Originally Posted by Geek_Guest View Post
    How to find submatix with max sum
    Sorry.... cud u ellaborate the Question..

  3. #3
    Expert Member
    Join Date
    Mar 2012

    Re: How to find submatix with max sum

    List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.

    Let us consider inputArr[m][n] be the input array.
    And let us make another array outputArr[m][n] with all fields set to zero by default.
    Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].

    So determine outputArr[i][j] =
    inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]

    Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
    sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]

    Now we can run an algorithm

    For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
About us
Applying for a job can be a stressful and frustrating experience, especially for someone who has never done it before. Considering that you are competing for the position with a at least a dozen other applicants, it is imperative that you thoroughly prepare for the job interview, in order to stand a good chance of getting hired. That's where GeekInterview can help.