Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>About recovering the actual submatrix, and not just the maximum sum, here's what I got. Sorry I do not have time to translate my code to your java version, so I'm posting my Ruby code with some comments in the key parts</p> <pre class="lang-rb prettyprint-override"><code>def max_contiguous_submatrix_n3(m) rows = m.count cols = rows ? m.first.count : 0 vps = Array.new(rows) for i in 0..rows vps[i] = Array.new(cols, 0) end for j in 0...cols vps[0][j] = m[0][j] for i in 1...rows vps[i][j] = vps[i-1][j] + m[i][j] end end max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right] # these arrays are used over Kadane sum = Array.new(cols) # obvious sum array used in Kadane pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j for i in 0...rows for k in i...rows # Kadane over all columns with the i..k rows sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane pos.fill(0) local_max = 0 # we keep track of the position of the max value over each Kadane's execution # notice that we do not keep track of the max value, but only its position sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0]) for j in 1...cols value = vps[k][j] - (i==0 ? 0 : vps[i-1][j]) if sum[j-1] &gt; 0 sum[j] = sum[j-1] + value pos[j] = pos[j-1] else sum[j] = value pos[j] = j end if sum[j] &gt; sum[local_max] local_max = j end end # Kadane ends here # Here's the key thing # If the max value obtained over the past Kadane's execution is larger than # the current maximum, then update the max array with sum and bounds if sum[local_max] &gt; max[0] # sum[local_max] is the new max value # the corresponding submatrix goes from rows i..k. # and from columns pos[local_max]..local_max # the array below contains [max_sum,top,left,bottom,right] max = [sum[local_max], i, pos[local_max], k, local_max] end end end return max # return the array with [max_sum,top,left,bottom,right] end </code></pre> <p>Some notes for clarification:</p> <p>I use an array to store all the values pertaining to the result for convenience. You can just use five standalone variables: max, top, left, bottom, right. It's just easier to assign in one line to the array and then the subroutine returns the array with all the needed information.</p> <p>If you copy and paste this code in a text-highlight-enabled editor with Ruby support you'll obviously understand it better. Hope this helps!</p>
    singulars
    1. This table or related slice is empty.
    1. POGetting the submatrix with maximum sum?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USkinshuk4
    1. USErnesto
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POGetting the submatrix with maximum sum?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHello Ernesto, i just saw your answer, thank you very much for effort. I'll look into your implementation shortly.
      singulars
      1. PO
      1. USguirgis
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload