Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def find_max_sum_submatrix(matrix):
- rows = len(matrix)
- columns = len(matrix[0])
- temp = [[0 for i in range(rows+1)] for j in range(columns+1)]
- for i in range(rows+1):
- for j in range(columns+1):
- if i == 0 or j == 0:
- temp[i][j] = 0
- else:
- temp[i][j] = temp[i-1][j] + temp[i][j-1] - temp[i-1][j-1] + matrix[i-1][j-1]
- max_sum = -1000000
- for i in range(rows):
- for j in range(i, rows):
- for m in range(columns):
- for n in range(m, columns):
- submatrix_sum = temp[j+1][n+1] - temp[j+1][m] - temp[i][n+1] + temp[i][m]
- if submatrix_sum > max_sum:
- max_sum = submatrix_sum
- return max_sum
- row_size, col_size = input().split()
- row_size = int(row_size)
- col_size = int(col_size)
- matrix = [[0 for i in range(col_size)] for j in range(row_size)]
- count = 0
- for i in range(row_size):
- row = [char for char in input().split()]
- for j in range(col_size):
- matrix[i][j] = int(row[j])
- print("Max submatrix:", find_max_sum_submatrix(matrix))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement