A round greenhouse has its planting beds on the inside of a cylinder. Unrolled, the beds form an m x n grid grid of integers (the expected profit of each bed, possibly negative). Rows run from the floor upwards and do not wrap, but the columns go all the way round, so column n - 1 sits right next to column 0.
A patch is a block of beds made of a contiguous range of rows and a contiguous arc of columns. The arc may pass from column n - 1 to column 0, and it may be the whole ring (all n columns). A patch must contain at least one bed.
Return the largest total profit of any patch.
Examples
Input: grid = [[3, -5, -5, 4], [2, -1, -6, 1]]
Output: 10
Explanation: rows 0-1 with the arc of columns 3, 0 gives 4 + 3 + 1 + 2 = 10.
Input: grid = [[-3, -1], [-2, -4]]
Output: -1
Input: grid = [[2, -1, 3], [1, 1, 1]]
Output: 7
Explanation: the whole greenhouse is the best patch.
Constraints
1 <= m <= 50,1 <= n <= 200-10**4 <= grid[r][c] <= 10**4- Checking every patch separately is far too slow for the largest grids.
Goals
- Reduce a rectangle search to a one-dimensional search by fixing a band of rows
- Find the best circular stretch with Kadane's algorithm run for both the maximum and the minimum
- Keep a patch non-empty when every value is negative