Sum of Distinct Values on the Borders of All Maximum-Sum Square Frames

You are given a rectangular matrix of integers and an integer frame_size. A frame is any square submatrix made of frame_size consecutive rows and frame_size consecutive columns. The border of a frame is the set of its cells that lie in its first row, last row, first column or last column; the cells inside it are not part of the border. The border sum of a frame is the sum of the values in its border cells, each cell counted once.

First find the maximum border sum over all frames. Then take every frame whose border sum equals that maximum, collect the values in all of their border cells, and return the sum of the distinct values in that collection.

Function Signature

def max_frame_distinct_sum(matrix: list[list[int]], frame_size: int) -> int:

Rules

• Frames are axis-aligned. A frame's top-left cell can be any (r, c) with r + frame_size <= R and c + frame_size <= C, where R and C are the numbers of rows and columns.
• When frame_size is 1, the border is the single cell. When frame_size is 2, every cell of the frame is on its border.
• Distinctness is by value, across the union of the borders of all maximum frames: a value that appears on the borders of two maximum frames, or twice on one border, is added once.
• Values from frames whose border sum is below the maximum are ignored, even if the same cells belong to a maximum frame's interior.
• Negative values are added as they are.

Constraints

• 1 <= R, C <= 100, where R = len(matrix) and C = len(matrix[0]); every row has length C.
• 1 <= frame_size <= min(R, C)
• -10^4 <= matrix[i][j] <= 10^4
• The absolute value of the answer is at most 50,005,000, which fits in a 32-bit signed integer.

Examples

Example 1

Input: matrix = [
 [1, 2, 3, 4],
 [5, 100, 7, 8],
 [9, 10, 11, 12]
], frame_size = 3
Output: 150

There are two frames. The frame over columns 0 to 2 has border cells 1, 2, 3, 5, 7, 9, 10, 11 with sum 48; the 100 is inside it, not on its border. The frame over columns 1 to 3 has border cells 2, 3, 4, 100, 8, 10, 11, 12 with sum 150; here the 100 is in its first column. Only the second frame has the maximum sum, and its distinct border values add up to 150.

Example 2

Input: matrix = [
 [1, 1, 1],
 [1, 5, 1],
 [1, 1, 1]
], frame_size = 2
Output: 6

All four 2 by 2 frames contain the center 5 and three 1s, so each has border sum 8 and all four are maximum frames. The distinct values on their borders are 1 and 5, so the answer is 6.

Example 3

Input: matrix = [
 [3, 7],
 [7, -2]
], frame_size = 1
Output: 7

Each cell is its own frame. The maximum border sum is 7, reached by two frames, and the only distinct value among them is 7.