获取最大金额的子阵？ [英] Getting the submatrix with maximum sum?

问题描述

输入：一个2维数组的N×N - 矩阵 - 有积极和消极因素

输出：任何尺寸，这样的一个子矩阵的总和就是所有可能的子矩阵中的最大值。

Input: A 2-dimensional array NxN - Matrix - with positive and negative elements.

Output: A submatrix of any size such that its summation is the maximum among all possible submatrices.

要求：算法复杂度是 O（N ^ 3）

Requirement: Algorithm complexity to be of O(N^3)

历史：随着Algorithmist，拉里和Kadane的算法的修改的帮助下，我设法解决这个问题的部分这是确定的总和只有 - 在下面Java语言。
由于埃内斯托谁设法解决该确定的矩阵，即左上角，右下角的边界问题的其余部分 - 在下面的Ruby

History: With the help of the Algorithmist, Larry and a modification of Kadane's Algorithm, i managed to solve the problem partly which is determining the summation only - below in Java.
Thanks to Ernesto who managed to solve the rest of the problem which is determining the boundaries of the matrix i.e. top-left, bottom-right corners - below in Ruby.

推荐答案

关于恢复实际的子矩阵，而不仅仅是最高金额，这是我得到了。对不起，我没有时间去翻译我的code到Java版本，所以我张贴我的红宝石code，在关键部位的一些评论

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

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 Kandane
  sum = Array.new(cols) # obvious sum array used in Kandane
  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
      # Kandane over all columns with the i..k rows
      sum.fill(0) # clean both the sum and pos arrays for the upcoming kandane
      pos.fill(0)
      local_max = 0 # we keep track of the position of the max value over each Kandane'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] > 0
          sum[j] = sum[j-1] + value
          pos[j] = pos[j-1]
        else
          sum[j] = value
          pos[j] = j
        end
        if sum[j] > sum[local_max]
          local_max = j
        end
      end
      # Kandane ends here

      # Here's the key thing
      # If the max value obtained over the past kandane's execution is larger than
      # the current maximum, then update the max array with sum and bounds
      if sum[local_max] > 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

澄清一些注意事项：

Some notes for clarification:

我使用一个数组来存储所有有关的结果为方便的值。你可以只使用五种独立的变量：最大，上，左，下，右。它只是更容易在同一行到数组赋值，然后子程序返回所有需要的信息的阵列。

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.

如果您复制并粘贴此code文本高亮功能的编辑器与Ruby的支持，你会明显地更好地理解它。希望这有助于！

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!

这篇关于获取最大金额的子阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！