All problems

Orchard Best Plot

Medium · prefix sum

An orchard is laid out as a grid of trees. The grid apples has one row per row of trees, and apples[r][c] is the number of apples on the tree in row r, column c.

You want to buy one square plot that covers exactly k rows and k columns of trees, so it holds k * k trees. The plot must lie completely inside the orchard: it cannot hang over an edge, and it cannot be rotated.

Return the largest total number of apples that any such plot can hold. The grid is not necessarily a square, but k is never bigger than the number of rows or the number of columns, so at least one plot always exists.

Examples

Example 1

Input: apples = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 2

Output: 28

The plot in the bottom-right corner holds 5 + 6 + 8 + 9 = 28 apples, more than any other 2 by 2 plot.

Example 2

Input: apples = [[1, 0, 0], [0, 0, 6], [0, 3, 2]], k = 2

Output: 11

The bottom-right plot holds 0 + 6 + 3 + 2 = 11. The other three plots hold 1, 6 and 3.

Example 3

Input: apples = [[5]], k = 1

Output: 5

Constraints

• 1 <= len(apples), len(apples[0]) <= 100
• Every row of apples has the same length.
• 0 <= apples[r][c] <= 1000
• 1 <= k <= min(number of rows, number of columns)