Voltar

Submatriz com soma máxima - Paradigmas

0 Curtidas
/* Dynamic Programming: Maximum Submatrix Sum
   =================================================================
   Description: Given a matrix with n rows and m columns, find
                the rectangular submatrix with the largest sum.
   
   Complexity:  O(n*m^2)
   -----------------------------------------------------------------
   Author:      Ashley Zinyk
   Date:        December 09, 2002
   References:  
   -----------------------------------------------------------------
   Reliability: 3 (Spain 108, 836, 10074)
   Notes: This code can easily be converted to work with a
          matrix of doubles.  Matricies have the coordinate (0,0) in
          the upper left corner and (n-1,m-1) in the lower right.
          Submatricies are inclusive, i.e. the submatrix
          (t=5, b=6, l=3, r=4) contains the elements:
          (5,3), (5,4), (6,3), (6,4).
          The result is not guaranteed to be unique.
*/

/* fix compile warning */

#include 
#define MAXN 100
#define Atype double

typedef struct {
  int top, bot, left, right;
  Atype sum;
} submat_t;

submat_t max_submatrix(Atype vals[MAXN][MAXN], int n, int m) {
  submat_t best, prev[MAXN][MAXN];
  int row, i, j;
  Atype sum;

  for (i = 0; i < n; i++)
    for (j = 0; j <= i; j++) prev[i][j].sum = -1;
  best.sum = vals[0][0];
  best.left = best.right = best.top = best.bot = 0;

  for (row = 0; row < n; row++) {
    for (i = 0; i < m; i++) {
      for (sum = 0, j = i; j < m; j++) {
        sum += vals[row][j];
        if (prev[i][j].sum <= 0) {
          prev[i][j].sum = 0;
          prev[i][j].top = row;
        }
        prev[i][j].sum += sum;
        if (prev[i][j].sum > best.sum) { /* put tie-breaking here */
          best = prev[i][j];
          best.right = j;
          best.left = i;
          best.bot = row;
        }
      }
    }
  }
  return best;
}

/* If you have matricies that are long and skinny (like 7x40 or 100x20)
   call this function instead of max_submatrix.  If the problem can be
   solved faster by transposing the matrix, this function will
   automatically determine that and solve the problem.  Its usage
   is identical to max_submatrix. */

submat_t max_submat_t(Atype mat[MAXN][MAXN], int n, int m) {
  Atype transp[MAXN][MAXN];
  int i, j, tmp;
  submat_t res;

  if (m <= n) return max_submatrix(mat, n, m);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) transp[j][i] = mat[i][j];
  res = max_submatrix(transp, m, n);
  tmp = res.top;
  res.top = res.left;
  res.left = tmp;
  tmp = res.bot;
  res.bot = res.right;
  res.right = tmp;
  return res;
}

int main() {
  Atype mat[100][100];
  int nrows, ncols, i, j;
  submat_t max;

  while (scanf("%d %d", &nrows, &ncols)==2) {
    for (i = 0; i < nrows; i++)
      for (j = 0; j < ncols; j++)
        scanf("%lf",&mat[i][j]);
    max = max_submatrix(mat,nrows,ncols);
    printf("(%d,%d) (%d,%d) has a sum of %g.\n",
           max.top, max.left, max.bot, max.right, max.sum);
  }
  return 0;
}
Problemas relacionados
  Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo
Sugestão de livro

Comentários


Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.