7
$\begingroup$

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge.

Given:A Matrix (Not necessarily square) filled with negative and positive integers.What will be good way of finding the sub matrix with the largest sum and this sub matrix may not be contiguous such that you can select columns 1 and 3 and rows 1 and 3 and leave out column 2 and row 2? Any hints/suggestions/tricks will help a lot.

  • 0
    So the submatrix can be whatever (rectangular) shape you want? So for example, if all entries except one were negative, and the remaining one were "30", the answer would be 30? It seems like a fairly complicated task :)2012-10-02
  • 0
    @rschwieb:no actually the requirement is to find the submatrix itself not the sum .ie you have the column and the row extent and the rows and columns included in the submatrix as the answer.It is not required to find the max sum itself2012-10-03
  • 0
    In the case I described, the submatrix is $[30]$ itself. If that is not the case then I still don't know what you mean by submatrix.2012-10-03
  • 0
    @rschwieb:I mean i just need to know the column number say C and row number R of [30] and the row extent=1 and column extent=1 (row extent is how much the row extends from the origin) Origin can be given as the left top most indices of the sub matrix2012-10-03

1 Answers 1