# Sliding Window - Painting The Barn (Gold)

I’m having trouble understanding how the external solution manages to find the two rectangles using the subarrays.

More specifically,

• what do `topDP[i], bottomDP[i], leftDP[i], rightDP[i]` represent? (for all i)
• How are these values calculated using the code below?
• From this, how can we find the two rectangles we need for the answer?

I’ve done my best to understand from the official editorial, but to no avail.
Thanks!!

``````for (int lhs = 0; lhs <= 200; lhs++)
{
for (int len = 1; lhs + len <= 200; len++)
{
int topSum = 0;
int leftSum = 0;
int rightSum = 0;
int bottomSum = 0;
for (int i = 1; i <= 200; i++)
{
ret = max(ret, topDP[i] = max(topDP[i], topSum = max(0, topSum + rectangleSum(i - 1, lhs, 1, len))));
ret = max(ret, leftDP[i] = max(leftDP[i], leftSum = max(0, leftSum + rectangleSum(lhs, i - 1, len, 1))));
ret = max(ret, rightDP[i] = max(rightDP[i], rightSum = max(0, rightSum + rectangleSum(lhs, 200 - i, len, 1))));
ret = max(ret, bottomDP[i] = max(bottomDP[i], bottomSum = max(0, bottomSum + rectangleSum(200 - i, lhs, 1, len))));
}
}
}
for (int i = 2; i <= 200; i++)
{
topDP[i] = max(topDP[i], topDP[i - 1]);
leftDP[i] = max(leftDP[i], leftDP[i - 1]);
rightDP[i] = max(rightDP[i], rightDP[i - 1]);
bottomDP[i] = max(bottomDP[i], bottomDP[i - 1]);
}

for (int i = 1; i <= 199; i++)
{
ret = max(ret, topDP[i] + bottomDP[200 - i]);
ret = max(ret, leftDP[i] + rightDP[200 - i]);
}``````

First, consider only solving for one rectangle. The code iterates through all pairs of column combinations (`lhs`, `lhs + len`), and the rectangle has columns `lhs` and `lhs + len`. Then it iterates down the rows, and doing a sliding window to figure out the maximum number of cells that can be painted with K layers for the current rectangle.

For two rectangles, there must exist a line between them (because they don’t overlap). The code contains 4 arrays to simulate the line. For example,` topDP[i]` means the maximum number of cells that can be painted with a rectangle above row `i`. Therefore, `topDP[i] + bottomDP[i]` means that the one rectangle is above `i`, and one below `i`.