Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.13 KB | None | 0 0
  1. def find_max_sum_submatrix(matrix):
  2.     rows = len(matrix)
  3.     columns = len(matrix[0])
  4.     temp = [[0 for i in range(rows+1)] for j in range(columns+1)]
  5.     for i in range(rows+1):
  6.         for j in range(columns+1):
  7.             if i == 0 or j == 0:
  8.                 temp[i][j] = 0
  9.             else:
  10.                 temp[i][j] = temp[i-1][j] + temp[i][j-1] - temp[i-1][j-1] + matrix[i-1][j-1]
  11.  
  12.     max_sum = -1000000
  13.     for i in range(rows):
  14.         for j in range(i, rows):
  15.             for m in range(columns):
  16.                 for n in range(m, columns):
  17.                     submatrix_sum = temp[j+1][n+1] - temp[j+1][m] - temp[i][n+1] + temp[i][m]
  18.                     if submatrix_sum > max_sum:
  19.                         max_sum = submatrix_sum
  20.  
  21.     return max_sum
  22.  
  23.  
  24. row_size, col_size = input().split()
  25. row_size = int(row_size)
  26. col_size = int(col_size)
  27. matrix = [[0 for i in range(col_size)] for j in range(row_size)]
  28. count = 0
  29.  
  30. for i in range(row_size):
  31.     row = [char for char in input().split()]
  32.     for j in range(col_size):
  33.         matrix[i][j] = int(row[j])
  34.  
  35. print("Max submatrix:", find_max_sum_submatrix(matrix))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement